Diechaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eineuniverselle Turingmaschine für eine beliebige Eingabe anhält.
ist ein Beispiel für eine nichtberechenbare Zahl. Sie ist nachGregory Chaitin definiert als
wobei die Summe über alle haltenden Programme gemeint ist (alle Programme, die ohne Eingabe nach endlicher Laufzeit halten) und die Länge des Programms inBit bezeichnet. Das bedeutet also, dass jedes haltende Programm der Länge m Bit das m-te Bit der Binärdarstellung von um 1 erhöht.
Bemerkung: Da es gewisse Freiheiten gibt, universelle Turingmaschinen zu definieren, hängt der genaue Wert der Konstante von der gewählten Maschinendefinition ab.
Durch Kenntnis der ersten n Bit der Konstante lässt sich dasHalteproblem für bis zu n Bit lange Programme entscheiden, sodass sich durchgenaue Kenntnis der ersten paar tausend Bit der Konstante viele interessante Probleme der Mathematik lösen ließen.
Ist gleich der Anzahl von haltenden Programme mit einer Länge von[1]
Der Algorithmus zur Berechnung von bei bekanntem inPseudocode lautet:[1]
Ω = Chaitinsche KonstanteΩ(a,b) = Wahrscheinlichkeit, dass ein Programm der Länge a in b Schritten hältΩ(a) = Grenzwert von Ω(a,b), wenn b gegen unendlich gehtK(a,b) = Anzahl der Programme der Länge a, die in b Schritte haltenk = 0While Ω(k,k)[n] != Ω[n] k = k + 1Ω(n) = K(k,k) / 2**n
Dabei sind a[n] die ersten n binären Nachkommastellen von a
Da aber eine nicht berechenbare Zahl ist, lässt sich dieser Algorithmus in der Praxis nicht anwenden.
Die besonderen Eigenschaften, welche der chaitinschen Konstante zugeschrieben werden, sind eine Folge daraus, dass man aus dieHaltesequenz rekonstruieren kann.[1]
Da dasHalteproblem aber nicht lösbar ist, kann nichtberechenbar sein und ist also einetranszendente reelle Zahl.
Eine Forschergruppe umCristian Calude von derUniversität Auckland bestimmte im Jahr 2002 durch Überprüfen aller Turingprogramme von bis zu 80 Bit Länge die ersten 64 Bit der Zahl.[2]