Chaitinsche Konstante
aus Wikipedia, der freien Enzyklopädie
Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält. Sie ist nach Gregory Chaitin definiert als
wobei p ein haltendes Programm ist und | p | die Länge des Programms in Bits bezeichnet.
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 das Halteproblem für bis zu n bit lange Programme entscheiden, sodass sich durch genaue Kenntnis der ersten paar tausend bit der Konstante viele interessante Probleme der Mathematik lösen ließen.
[Bearbeiten] Literatur
Eric W. Weisstein: Chaitin's Constant, MathWorld--A Wolfram Web Resource
[Bearbeiten] Weblinks
- Die ersten 64 Bit einer chaitinschen Konstante: Cristian S. Calude's Website
