20.500.12556/RUL-83715 Chaitinova konstanta Omega - od definicije do danes Chaitin's constant Omega - from definition to present 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. 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. Omega Chaitinova konstanta verjetnost ustavitve problem ustavitve neizračunljivost naključnost Turingov stroj Omega Chaitin's constant halting probability halting problem uncomputability randomness Turing machine true false false Slovenski jezik Angleški jezik Diplomsko delo 2016-06-23 15:20:05 2016-06-23 15:20:06 2022-08-02 00:13:45 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 17689 Selak_Metka_-_Chaitinova_konstanta_Omega_-_od_definicije_do_danes.pdf Selak_Metka_-_Chaitinova_konstanta_Omega_-_od_definicije_do_danes.pdf 1 573D28A69E9EB33F9D252B82F2B3044D d319c5bb6f387a673862e8eed3f2896749c6dd3598bb01554ef4a0be84b06748 5451fbe1-a1ae-11eb-a523-00155dcfd717 20.500.12556/rul/09d51eaa-6728-45c2-bf57-d3530ca0e6fe https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=86752 Fakulteta za računalništvo in informatiko 0 0 0