Chaitinsche Konstante - LinkFang.de





Chaitinsche Konstante


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

[math]\Omega[/math] ist ein Beispiel für eine nicht berechenbare Zahl. Sie ist nach Gregory Chaitin definiert als

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

wobei die Summe über alle haltenden Programme [math]p[/math] gemeint ist (alle Programme, die ohne Eingabe nach endlicher Laufzeit halten) und [math]|p|[/math] 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 [math]\Omega[/math] 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 [math]\Omega[/math] 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.

Literatur

Weblinks


Kategorien: Theoretische Informatik | Besondere Zahl

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Chaitinsche Konstante (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.