Chaitinova konstanta Omega - od definicije do danesSELAK, METKA (Avtor) Robič, Borut (Mentor) OmegaChaitinova konstantaverjetnost ustavitveproblem ustavitveneizračunljivostnaključnostTuringov strojV 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.20162016-06-23 15:20:05Diplomsko delo83715VisID: 17689sl