Chaitinsche Konstante

Chaitinsche Konstante

Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält.

Ω ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als

\Omega=\sum_{p\ \mathrm{h\ddot a lt}}2^{-\left|p\right|}

wobei die Summe über alle haltenden Programme p gemeint ist (alle Programme, die ohne Eingabe nach endlicher Laufzeit halten) und | p | die Länge des Programms in Bit 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 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.

Da das Halteproblem aber nicht lösbar ist, kann Ω nicht berechenbar sein und ist also eine transzendente reelle Zahl.

Eine Forschergruppe um Christian Calude von der Universität Auckland bestimmte im Jahr 2002 durch Überprüfen aller Turingprogramme von bis zu 80 Bit Länge die ersten 64 Bit der Zahl. Hierbei ist allerdings anzumerken, dass sich aufgrund des Aufbaus der Zahl eine Änderung an irgendeiner Dezimalstelle der Zahl auf alle vorigen auswirken kann, weshalb es unmöglich ist, die „tatsächlichen“ ersten Ziffern der Zahl zu bestimmen.

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Chaitins Konstante — Die chaitinsche Konstante gibt die Wahrscheinlichkeit an, mit der eine universelle Turingmaschine für eine beliebige Eingabe anhält. Ω ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als wobei die Summe… …   Deutsch Wikipedia

  • Liste mathematischer Konstanten — Eine mathematische Konstante ist eine fest definierte spezielle reelle oder komplexe Zahl, die sich auf natürliche Weise in der Mathematik ergibt. Anders als physikalische Konstanten werden mathematische Konstanten unabhängig von jedem… …   Deutsch Wikipedia

  • Mathematische Konstanten — Eine mathematische Konstante ist eine fest definierte spezielle reelle oder komplexe Zahl, die sich auf natürliche Weise in der Mathematik ergibt. Anders als physikalische Konstanten werden mathematische Konstanten unabhängig von jedem… …   Deutsch Wikipedia

  • My-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • My-rekursive Funktion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Partiell-rekursive Funktion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Μ-Operator — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Μ-Rekursion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Μ-rekursive Funktion — Die Klasse Pr der μ rekursiven Funktionen oder partiell rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Sie beschreibt die Menge aller Funktionen, die im intuitiven Sinn… …   Deutsch Wikipedia

  • Chaitin — Gregory J. Chaitin (* 1947 in Chicago) ist ein US amerikanischer Mathematiker und Philosoph. Sein Hauptarbeitsgebiet ist die Berechenbarkeitstheorie. Er steht damit in der Tradition von Kurt Gödel und Alan Turing, deren Theoreme… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”