Chaitins konstant

I beräkningsteori är Chaitins konstant, Ω, ett tal som representerar sannolikheten för att ett slumpmässigt sammansatt datorprogram terminerar. Mer precist finns oändligt många olika Chaitins konstanter, en för varje beräkningsmodell eller programspråk. Konceptet studerades ursprungligen av Gregory Chaitin.

Chaitins konstant är ett normalt och transcendent tal. Dess mest anmärkningsvärda egenskap är att det är definierbart men trots det oberäkningsbart. Anledningen är att en algoritm som har tillgång till de första n bitarna av Ω skulle kunna lösa stopproblemet för n bitar långa program, men stopproblemet är olösbart och därmed kan Ω inte beräknas för tillräckligt stora n.

Calude, Dinneen och Shu har bestämt de första 64 bitarna av Chaitins konstant för en viss beräkningsmodell. De är

0,00000 01000 00010 00001 10001 00001 10100 01111 11001 01110 11101 00001 0000...

vilket motsvarar decimaltalet

0,00787 49969 97812 3844...

Källor