Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Chaitinsche Konstante aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Chaitinsche Konstante

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
:$\backslash Omega=\backslash sum\_\{p$
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.

Literatur

Eric W. Weisstein: Chaitin's Constant, [http://mathworld.wolfram.com/ChaitinsConstant.html MathWorld--A Wolfram Web Resource]

Weblinks

* Die ersten 64 Bit einer chaitinschen Konstante: [http://www.cs.auckland.ac.nz/~cristian/ Cristian S. Calude's Website]

       VIDEO-NEWS UND ANGEBOTE