Im Informatik-Teilfeld der algorithmischen Informationstheorie ein Chaitin ist unveränderliche oder stockende Wahrscheinlichkeit eine reelle Zahl, die informell die Wahrscheinlichkeit vertritt, dass ein zufällig gebautes Programm hinken wird. Diese Zahlen werden von einem Aufbau wegen Gregory Chaitins gebildet.

Obwohl es ungeheuer viele stockende Wahrscheinlichkeiten gibt, ist es üblich, den Brief Ω zu verwenden, um sich auf sie zu beziehen, als ob es nur einen gab. Weil Ω von der verwendeten Programm-Verschlüsselung abhängt, wird es manchmal den Aufbau von Chaitin statt der Konstante von Chaitin wenn nicht das Verweisen zu jeder spezifischen Verschlüsselung genannt.

Jede stockende Wahrscheinlichkeit ist eine normale und transzendentale reelle Zahl, die nicht berechenbar ist, was bedeutet, dass es keinen Algorithmus gibt, der seine Ziffern aufzählt.

Hintergrund

Die Definition einer stockenden Wahrscheinlichkeit verlässt sich auf die Existenz von universalen berechenbaren Funktionen ohne Präfixe. Solch eine Funktion vertritt intuitiv eine Programmiersprache mit dem Eigentum, dass kein gültiges Programm als eine richtige Erweiterung eines anderen gültigen Programms erhalten werden kann.

Nehmen Sie an, dass F eine teilweise Funktion ist, die ein Argument, eine begrenzte binäre Schnur nimmt, und vielleicht eine einzelne binäre Schnur als Produktion zurückgibt. Die Funktion F wird berechenbar genannt, wenn es eine Maschine von Turing gibt, die sie schätzt.

Die Funktion F wird universal genannt, wenn das folgende Eigentum hält: Für jede berechenbare Funktion f einer einzelnen Variable gibt es eine Schnur w solch das für den ganzen x, F (w x) = f (x); hier w vertritt x die Verkettung der zwei Schnuren w und x. Das bedeutet, dass F verwendet werden kann, um jede berechenbare Funktion einer Variable vorzutäuschen. Informell vertritt w eine "Schrift" für die berechenbare Funktion f, und F vertritt einen "Dolmetscher", der die Schrift als ein Präfix seines Eingangs grammatisch analysiert und sie dann auf dem Rest des Eingangs durchführt.

Bemerken Sie, dass für irgendwelchen w befestigt hat, ist die Funktion f (x) = F (w x) berechenbar; so stellt das Allgemeinheitseigentum fest, dass alle berechenbaren Funktionen einer Variable auf diese Mode erhalten werden können.

Das Gebiet von F ist der Satz aller Eingänge p, auf dem es definiert wird. Für F, die universal sind, kann solch ein p allgemein sowohl als die Verkettung eines Programm-Teils als auch als ein Datenteil, und als ein einzelnes Programm für die Funktion F gesehen werden.

Die Funktion F wird ohne Präfixe genannt, wenn es keine zwei Elemente p, p&prime gibt; in seinem solchem Gebiet dass p′ ist eine richtige Erweiterung von p. Das kann als umformuliert werden: Das Gebiet von F ist ein Code ohne Präfixe (sofortiger Code) auf dem Satz von begrenzten binären Schnuren. Eine einfache Weise, freies Vorgebirge des Präfixes geltend zu machen, soll Maschinen verwenden, deren Mittel des Eingangs ein binärer Strom ist, von dem Bit einer nach dem anderen gelesen werden können. Es gibt keinen Anschreiber des Endes des Stroms; das Ende des Eingangs wird dadurch bestimmt, wenn sich die universale Maschine dafür entscheidet aufzuhören, mehr Bit zu lesen. Hier wird der Unterschied zwischen den zwei Begriffen des im letzten Paragrafen erwähnten Programms klar; einer wird durch eine Grammatik leicht anerkannt, während der andere verlangt, dass willkürliche Berechnung anerkennt.

Das Gebiet jeder universalen berechenbaren Funktion ist berechenbar enumerable Satz, aber nie ein berechenbarer Satz. Das Gebiet ist immer zum stockenden Problem gleichwertiger Turing.

Definition

Lassen Sie P das Gebiet einer universalen berechenbaren Funktion ohne Präfixe F sein. Der unveränderliche Ω wird dann als definiert

:

wo die Länge einer Schnur p anzeigt.

Das ist eine unendliche Summe, die einen summand für jeden p im Gebiet von F hat. Die Voraussetzung, dass das Gebiet, zusammen mit der Ungleichheit von Kraft ohne Präfixe sein, sicherstellt, dass diese Summe zu einer reellen Zahl zwischen 0 und 1 zusammenläuft. Wenn F vom Zusammenhang dann Ω klar ist, kann einfach Ω angezeigt werden, obwohl verschiedene universale berechenbare Funktionen ohne Präfixe zu verschiedenen Werten von Ω führen.

Beziehung zum stockenden Problem

Die ersten Bit wissend, konnte man das stockende Problem für alle Programme einer Größe bis dazu berechnen. Lassen Sie das Programm, für das das stockende Problem behoben werden soll, N Bit lange sein. Auf die genau passende Mode werden alle Programme aller Längen geführt, bis genug sind gehinkt, um genug Wahrscheinlichkeit gemeinsam beizutragen, um diese zuerst N Bit zu vergleichen. Wenn das Programm noch nicht gehinkt ist, dann wird es nie, da sein Beitrag zur stockenden Wahrscheinlichkeit die ersten N Bit betreffen würde.

So würde das stockende Problem dafür behoben.

Weil viele hervorragende Probleme in der Zahlentheorie, wie die Vermutung von Goldbach zum Beheben des stockenden Problems für spezielle Programme gleichwertig sind (der nach Gegenbeispielen und Halt grundsätzlich suchen würde, wenn man gefunden wird), wissend, dass genug Bit der Konstante von Chaitin auch bedeuten würden, die Antwort auf diese Probleme zu wissen. Aber weil das stockende Problem nicht allgemein lösbar ist, und deshalb das Rechnen von irgendwelchem, aber den ersten paar Bit der Konstante von Chaitin nicht möglich ist, reduziert das gerade harte Probleme auf unmögliche, viel wie das Versuchen, eine Orakel-Maschine für das stockende Problem zu bauen, würde sein.

Interpretation als eine Wahrscheinlichkeit

Der Kantor-Raum ist die Sammlung aller unendlichen Folgen von 0s und 1s. Eine stockende Wahrscheinlichkeit kann als das Maß einer bestimmten Teilmenge des Kantor-Raums unter dem üblichen Wahrscheinlichkeitsmaß auf dem Kantor-Raum interpretiert werden. Es ist von dieser Interpretation, dass stockende Wahrscheinlichkeiten ihren Namen nehmen.

Das Wahrscheinlichkeitsmaß auf dem Kantor-Raum, manchmal genannt das Maß der schönen Münze, wird definiert, so dass für jede binäre Schnur x der Satz von Folgen, die mit x beginnen, Maß 2 hat. Das deutet an, dass für jede natürliche Zahl n der Satz von Folgen f im solchem Kantor-Raum, dass f (n) = 1 Maß 1/2 hat, und der Satz von Folgen, deren n-tes Element 0 auch ist, Maß 1/2 hat.

Lassen Sie F eine universale berechenbare Funktion ohne Präfixe sein. Das Gebiet P F besteht aus einem unendlichen Satz von binären Schnuren

:.

Jede dieser Schnuren p bestimmt eine Teilmenge S vom Kantor-Raum; der Satz S enthält alle Folgen im Kantor-Raum, die mit p beginnen. Diese Sätze sind zusammenhanglos, weil P ein Satz ohne Präfixe ist. Die Summe

:

vertritt das Maß des Satzes

:.

Auf diese Weise vertritt Ω die Wahrscheinlichkeit, dass eine zufällig ausgewählte unendliche Folge von 0s und 1s mit wenig Schnur beginnt (etwas begrenzter Länge), der im Gebiet von F ist. Es ist aus diesem Grund, dass Ω eine stockende Wahrscheinlichkeit genannt wird.

Eigenschaften

Jeder Chaitin unveränderliche Ω hat die folgenden Eigenschaften:

• Es ist algorithmisch zufällig. Das bedeutet, dass das kürzeste Programm zur Produktion die ersten n Bit von Ω der Größe mindestens n-O (1) sein muss. Das ist, weil, als im Beispiel von Goldbach, jene n Bit uns ermöglichen, genau herauszufinden, welche Programme unter allen diejenigen der Länge am grössten Teil von n halten.
• Es ist eine normale Zahl, was bedeutet, dass seine Ziffern equidistributed sind, als ob sie dadurch erzeugt wurden, eine schöne Münze zu werfen.
• Es ist nicht eine berechenbare Zahl; es gibt keine berechenbare Funktion, die seine Binärentwicklung, wie besprochen, unten aufzählt.
• Der Satz von rationalen Zahlen q solch dass q

• Ω ist eine arithmetische Zahl.
• Es ist Turing, der zum stockenden Problem und so am Niveau der arithmetischen Hierarchie gleichwertig ist.

Nicht jeder Satz, der zum stockenden Problem gleichwertiger Turing ist, ist eine stockende Wahrscheinlichkeit. Eine feinere Gleichwertigkeitsbeziehung, Gleichwertigkeit von Solovay, kann verwendet werden, um die stockenden Wahrscheinlichkeiten unter dem nach-links-c.e zu charakterisieren. reals.

Unberechenbarkeit

Eine reelle Zahl wird berechenbar genannt, wenn es einen Algorithmus gibt, der, gegeben n, die ersten n Ziffern der Zahl zurückgibt. Das ist zur Existenz eines Programms gleichwertig, das die Ziffern der reellen Zahl aufzählt.

Keine stockende Wahrscheinlichkeit ist berechenbar. Der Beweis dieser Tatsache verlässt sich auf einen Algorithmus, der, in Anbetracht der ersten n Ziffern von Ω, das stockende Problem von Turing für Programme der Länge bis zu n behebt. Da das stockende Problem unentscheidbar ist, kann Ω nicht geschätzt werden.

Der Algorithmus geht wie folgt weiter. In Anbetracht der ersten n Ziffern von Ω und einem kn zählt der Algorithmus das Gebiet von F auf, bis genug Elemente des Gebiets gefunden worden sind, so dass die Wahrscheinlichkeit, die sie vertreten, innerhalb von 2 von Ω ist. Nach diesem Punkt kann kein zusätzliches Programm der Länge k im Gebiet sein, weil jeder von diesen 2 zum Maß beitragen würde, das unmöglich ist. So ist der Satz von Schnuren der Länge k im Gebiet genau der Satz solcher bereits aufgezählten Schnuren.

Unvollständigkeitslehrsatz für stockende Wahrscheinlichkeiten

Für jedes spezifische konsequente effektiv vertretene axiomatische System für die natürlichen Zahlen, wie Arithmetik von Peano, dort besteht ein unveränderlicher solcher N, dass, wie man beweisen kann, kein Bit von Ω nach dem N-ten ein oder Null innerhalb dieses Systems ist. Der unveränderliche N hängt ab, wie das formelle System effektiv vertreten wird, und so die Kompliziertheit des axiomatischen Systems nicht direkt widerspiegelt. Dieses Unvollständigkeitsergebnis ist dem Unvollständigkeitslehrsatz von Gödel ähnlich, in dem es zeigt, dass keine konsequente formelle Theorie für die Arithmetik abgeschlossen sein kann.

Superomega

Wie oben erwähnt sind die ersten n Bit des unveränderlichen Omegas von Gregory Chaitin zufällig oder incompressible im Sinn, dass wir sie durch einen stockenden Algorithmus mit weniger nicht schätzen können als n-O (1) Bit. Denken Sie jedoch das kurze, aber nie den stockenden Algorithmus, der systematisch verzeichnet und alle möglichen Programme führt; wann auch immer einer von ihnen hinkt, wird seine Wahrscheinlichkeit zur Produktion (initialisiert durch die Null) hinzugefügt. Nach der endlichen Zeit werden sich die ersten n Bit der Produktion mehr nie ändern (es ist nicht von Bedeutung, der dieses Mal selbst durch ein stockendes Programm nicht berechenbar ist). Also gibt es einen kurzen nichtstockenden Algorithmus, dessen Produktion (nach der endlichen Zeit) auf die ersten n Bit des Omegas zusammenläuft. Mit anderen Worten, der enumerable die ersten n Bit des Omegas sind im Sinn hoch komprimierbar, dass sie durch einen sehr kurzen Algorithmus mit der Grenze berechenbar sind; sie sind in Bezug auf den Satz nicht zufällig, Algorithmen aufzuzählen. Jürgen Schmidhuber (2000) hat ein mit der Grenze berechenbares "Superomega" gebaut, das gewissermaßen viel zufälliger ist als das ursprüngliche mit der Grenze berechenbare Omega, weil man das Superomega durch kein Aufzählen nichtstockender Algorithmus bedeutsam zusammenpressen kann.

Siehe auch

• Kompliziertheit von Kolmogorov
• Unvollständigkeitslehrsatz
• Cristian S. Calude (2002). Information und Zufälligkeit: Eine Algorithmische Perspektive, die zweite Ausgabe. Springer. Internationale Standardbuchnummer 3-5404-3466-6
• Cristian S. Calude, Michael J. Dinneen und Chi-Kou Shu. Die Computerwissenschaft eines Anblicks der Zufälligkeit.
• R. Downey und D. Hirschfeldt (2010), Algorithmische Zufälligkeit und Kompliziertheit, Monografie in der Vorbereitung, Springer-Verlag. Einleitende Version kann online gefunden werden.
• Ming Li und Paul Vitányi (1997). Eine Einführung in die Kompliziertheit von Kolmogorov und Seine Anwendungen. Springer. Einführungskapitel-voller Text.
• Jürgen Schmidhuber (2000). Algorithmische Theorien von Allem (arXiv: quant-ph/0011122). Zeitschriftenverweisung:J. Schmidhuber (2002). Hierarchien von verallgemeinerten Kompliziertheiten von Kolmogorov und nonenumerable universalen in der Grenze berechenbaren Maßnahmen. Internationale Zeitschrift von Fundamenten der Informatik 13 (4):587-612.

Außenverbindungen

• Omega, und warum Mathematik keinen Artikel TOE hat, der auf einem geschriebenem durch Gregory Chaitin gestützt ist, der in der Ausgabe im August 2004 der Mathematik Heute anlässlich des 50. Jahrestages des Todes von Alan Turing erschienen ist.
• Die Grenzen des Grunds, Gregory Chaitins, sind ursprünglich im Wissenschaftlichen Amerikaner, März 2006 erschienen.
• Mit der Grenze berechenbares Superomega, das zufälliger ist als Omega und Generalisationen der algorithmischen Information, durch Jürgen Schmidhuber