Chaitinova konstanta Omega - od definicije do danes

SELAK, METKA (author), Robič, Borut (mentor)

V delu je predstavljena problematika, ki je privedla do odkritja Chaitinove konstante Ω, ki je verjetnost ustavitve univerzalnega samoomejenega Turingovega stroja. Podana je njena definicija. Predstavljene so tudi njene zanimivejše lastnosti, med katerimi sta najpomembnejši naključnost in neizračunljivost. Konstanta Ω vnaša naključnost in neizračunljivost v različna področja matematike in računalništva, kar je velika težava za tradicionalen pristop k problemom, ki je še vedno prevladujoč. Predstavljene so tri prevedbe znanih problemov z različnih področij matematike, ki povezujejo bite konstante Ω z rešitvami teh problemov. V nalogi so povzete tudi novejše raziskave v zvezi s konstanto Ω, predvsem na področju računanja točnih začetnih bitov tega v celoti neizračunljivega števila. Na koncu pa je navedenih še nekaj primerov verjetnosti ustavitve pri praktičnih primerih. Predstavitev Chaitinove konstante Ω skuša biti kar se da intuitivna in ob uporabi le najnujnejšega matematičnega aparata še vedno natančna.

• Language: Slovenian
• Keywords: Omega, Chaitinova konstanta, verjetnost ustavitve, problem ustavitve, neizračunljivost, naključnost, Turingov stroj
• Work type: Undergraduate thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2016
• PID: 20.500.12556/RUL-83715
• Publication date in RUL: 23.06.2016

Secondary language

• Language: English
• Title: Chaitin's constant Omega - from definition to present

Abstract

Problems, that led to the discovery of Chaitin's constant Ω are presented in this work. The constant Ω is the halting probability of the universal self-delimited Turing machine. Its definition is given. Its interesting features are presented, among which randomness and uncomputability are the most important. The constant Ω brings randomness and uncomputability to different areas of mathematics and computer science. This is a great problem for the traditional approach to problem solving. Three transformations of famous problems from different areas of mathematics, which relate bits of Ω to solutions to these problems, are given. Recent researches connected whit the constant Ω, mainly about computing its exact initial bits, are presented. A few examples of the halting probability in practise are listed. The presentation of Chaitin's constant Ω tries to be as intuitive as possible and still exact, while using only the necessary mathematics.

• Keywords: Omega, Chaitin's constant, halting probability, halting problem, uncomputability, randomness, Turing machine