Chaitinova konstanta je primjer (zapravo obitelj primjera) ne-izračunljivog broja. predstavlja vjerojatnost da će se nasumično generirani program (u određenom modelu) zaustaviti. Može se približno izračunati, ali ne postoji (dokazivo) algoritam za njegovo izračunavanje proizvoljnom preciznošću.
Što čini broj izračunljivim?
Izračunljivi broj je broj koji se može izračunati konačnim računalnim programom. Svi brojevi za koje ste ikada čuli kao što su 3, √2, π, e, itd. su izračunljivi. Neki brojevi (poput π) predstavljeni su beskonačnim nizom znamenki koje se ne ponavljaju.
Što znači neizračunljivo?
Neizračunljiv je problem za koji ne postoji algoritam koji se može koristiti za njegovo rješavanje. Najpoznatiji primjer neuračunljivosti (ili neodlučivosti) je problem zaustavljanja.
Postoje li ne-izračunljivi brojevi?
Ne samo da postoje brojevi koji se ne mogu izračunati, nego su u stvari mnogo brojniji od izračunljivih brojeva. Mnogi, mnogi realni brojevi su jednostavno beskonačni nizovi naizgled slučajnih znamenki, bez uzorka ili posebnih svojstava. … Kao jedan takav primjer, razmotrite broj čiji je dio ispred decimalne točke 0.
Jesu li stvarni brojevi izračunljivi?
Realni broj je izračunljiv ako i samo ako je skup prirodnih brojeva koji predstavlja (kada je napisan u binarnom obliku i promatran kao karakteristična funkcija) izračunljiv. Svaki izračunljivbroj je aritmetički.
