Theorie der Information und Kreationismus: Algorithmische Informationstheorie (Chaitin, Solomonoff & Kolmogorov)

In diesem Artikel:

• Algorithmische Informationstheorie
• Turing-Maschinen und das Halteproblem
• Church-Turing-These
• Universelle Turing-Maschinen
• Kolmogorov-Komplexität
• Einige andere Konzepte
• Programme und selbstbegrenzende Codes
• Auswahl der UTM
• Chaitins Haltewahrscheinlichkeit: Omega
• Quellenangaben
• Links

Algorithmische Informationstheorie

Gregory Chaitin^[1], Ray Solomonoff, und Andrei Kolmogorov entwickelten eine andere Auffassung von Information als Shannon. Statt des statistischen Ensembles von Nachrichten aus einer Informationsquelle zu betrachten, betrachtet die algorithmische Informationstheorie individuelle Symbolfolgen. Hier wird Information H(X) als die minimale Größe eines Programms definiert, das notwendig ist, um die Sequenz X zu erzeugen.

Dieser Artikel hebt einige der Hauptkonzepte der Algorithmischen Informationstheorie hervor. Kenntnisse dieses Themas können nützlich sein, wenn man mit Kreationisten diskutiert, die Konzepte aus sowohl der klassischen als auch der algorithmischen Informationstheorie möglicherweise ungenau verwenden. Dieser Artikel ist lediglich eine Übersicht der wichtigsten Ideen. Für die mathematischen Beweise und detailliertere Hintergründe siehe das zitierte Material und die Links.

Turing-Maschinen und das Halteproblem[Oben]

Das Verständnis der algebraischen Informationstheorie erfordert Kenntnisse über Turing-Maschinen. Alan Turing^[2] zeigte, dass es möglich ist, eine einzelne Maschine U zu erfinden, die jede berechenbare Sequenz berechnen kann. Turgings Notationen sind etwas schwierig, aber die Grundidee ist wie folgt:

Die Elemente einer Turing-Maschine sind ein Programmband mit einem Lesekopf, ein Arbeitsband mit einem Leseschreibkopf, ein Zustand (dargestellt durch eine Zahl), eine Zustands­tabelle und eine Aktionstabelle. Das Programmband hat eine endliche Länge und enthält eine Sequenz von Symbolen. Das Arbeitsband ist zunächst leer. Für jeden Maschinenzyklus wird der Zustand durch den Lookup-Wert in der Zustands­tabelle ersetzt. Der Lookup-Index ist eine Kombination aus dem aktuellen Zustand, dem vom Programmband gelesenen Symbol und dem vom Arbeitsband gelesenen Symbol.

Die Aktionstabelle steuert die Bänder. Die folgenden Aktionen sind erlaubt:

1. Halte
2. Fördere das Programmband ein Symbol nach rechts
3. Fördere das Arbeitsband ein Symbol nach rechts
4. Spule das Arbeitsband ein Symbol nach links zurück
5. Lösche das aktuelle Symbol auf dem Arbeitsband
6. Schreibe eines der R-Symbole auf das Arbeitsband (es gibt R solcher Aktionen).

Wir können die Bänder der Turing-Maschine als Zeichenketten betrachten; das heißt, als Sequenzen von Symbolen. Wir werden die Programmzeichenkette p und die resultierende Ausgabezeichenkette auf dem Arbeitsband X nennen. Das Programm p erzeugt die Zeichenkette X auf der Turing-Maschine T. Da wir die Turing-Maschine T haben, kann die Zeichenkette X durch p dargestellt werden. Wir können p und X auch als Zahlen betrachten, da Zahlen als Symbolsequenzen dargestellt werden.

Öftersprechen wir über binäre Turing-Maschinen, für die das Zeichensatz auf den beiden Bändern aus 0 und 1 besteht. Dies muss jedoch nicht der Fall sein. Wir können eine beliebige Anzahl von Symbolen haben. Nun können wir natürlich nicht wirklich eine unendlich lange Arbeitsband haben, aber die Turing-Maschine wird für theoretische Probleme verwendet, sodass wir uns vorstellen können, dass wir dies tun.

Ein Diagramm einer Turing-Maschine ist unten dargestellt:

Fig. 1. Turing-Maschine

Für eine gute Beschreibung von Turing-Maschinen siehe die Stanford Encyclopedia of Philosophy^[3]. Beachten Sie, dass theoretische Turing-Maschinen unendliche Arbeitstapes besitzen, die natürlich nicht konstruiert werden können. Daher sind einige Probleme nicht auf tatsächlichen, physischen Turing-Maschinen ausführbar.

Turing erfand seine theoretische Maschine, um das Entscheidungsproblem oder Entscheidungsproblem zu lösen; das heißt, ob es in der symbolischen Logik möglich ist, einen allgemeinen Algorithmus zu finden, der für gegebene Aussagen erster Ordnung entscheidet, ob sie universell gültig sind oder nicht.

Die modernen Wurzeln des Entscheidungsproblems gehen auf eine Rede von 1900 zurück, die David Hilbert hielt. ^[4] Hilbert hatte gehofft, dass es möglich sein würde, einen allgemeinen Algorithmus zu entwickeln, um zu entscheiden, ob ein Satz von Axiomen widersprüchlich ist. Kurt Gödel ^[5] zeigte, dass in jedem axiomatischen System für die Arithmetik natürlicher Zahlen gewisse Aussagen existieren, die innerhalb der Axiome des Systems weder bewiesen noch widerlegt werden können. Dies ist als Gödels Unvollständigkeitssatz bekannt und demonstrierte, dass Hilberts Zweites Problem nicht gelöst werden konnte.

Turing, gestützt auf die Arbeit von Gödel, bewies, dass das Entscheidungsproblem unlösbar ist. Alonzo Church zeigte unabhängig von Turing dasselbe.

Turing nutzte das Halteproblem für seinen Beweis. Das Halteproblem ist ein Entscheidungsproblem. Es stellt die Frage: Gibt man eine Beschreibung eines Algorithmus und seine Anfangsbedingungen vor, kann man zeigen, dass der Algorithmus anhält? Ein Algorithmus, der die Ziffern von π erzeugt, ist ein Beispiel für einen nicht anhaltenden Algorithmus (π ist eine irrationale und transzendente Zahl; sie kann nicht als Polynom mit rationalen Koeffizienten ausgedrückt werden und hat daher eine unendliche Anzahl von Ziffern). Turing bewies, dass kein allgemeiner Algorithmus existiert, der das Halteproblem für alle möglichen Eingaben lösen kann, und folglich, dass das Entscheidungsproblem unlösbar ist.

Church-Turing-These [Oben]

Die Church-Turing-These ist eine Synthese der Church'schen These und der Turing'schen These. Sie besagt im Wesentlichen, dass, wenn es ein effektives Verfahren gibt, um die Werte einer mathematischen Funktion zu ermitteln, die Funktion von einer Turing-Maschine berechnet werden kann. Die grundlegende Idee ist, dass, wenn eine Berechnung von einer beliebigen (deterministischen) Maschine berechnet werden kann, die effektiv implementiert werden kann, eine Turing-Maschine diese Berechnung durchführen kann.

Zwei konkurrierende Auffassungen der Church-Turing-These wurden von Copeland^[6] und Hodges^[7] veröffentlicht (das Argument betrifft zumindest teilweise, wie stark formuliert eine These sein sollte, die Church und Turing hätten zugestimmt, und ob sie dem von Gandy als These M beschriebenen Konzept zugestimmt haben).

Universelle Turing-Maschine [Oben]

Es wäre nicht praktikabel, jede Zeit, wenn man eine Berechnung durchführen möchte, eine neue Turing-Maschine zu konstruieren, was zur Entstehung des Konzepts der Universalen Turing-Maschine (UTM) führte. Eine Universelle Turing-Maschine (UTM) wird definiert als eine Turing-Maschine, die jede andere Turing-Maschine simulieren kann. Wenn wir eine UTM haben, können wir sie programmieren, um sich wie jede Turing-Maschine zu verhalten, die wir wollen.

Da eine Turing-Maschine durch ihre Zustands- und Aktionstabellen beschrieben werden kann, lässt sie sich als Zeichenkette darstellen. Wenn p ein Programm auf einer Turing-Maschine T ist, das die Zeichenkette X auf dem Arbeitsband erzeugt, dann können wir auf einer universellen Turing-Maschine eine Zeichenketten-Darstellung von T laden, das Programm p ausführen und X erhalten. Wir verwenden das Symbol u für die Darstellung von T auf U. Daher gibt U bei Eingabe von <u><p> die Zeichenkette X aus. Beachten Sie, dass u von sowohl T als auch U abhängt, während p von X und T abhängt.

Es gibt eine unendliche Anzahl von Universalen Turing-Maschinen. Einige Forschungsarbeiten haben sich damit beschäftigt, herauszufinden, wie klein sie sein können. Marvin Minsky entdeckte 1962 eine 7-Zustands-4-Symbol-UTM^[8]. Yurii Rogozhin hat eine Reihe kleiner UTMs entdeckt^[9]. Wenn wir sie als (m, n) beschreiben, wobei m die Anzahl der Zustände und n die Anzahl der Symbole ist, hat Rogozhin zu Minskys (7, 4) die folgenden hinzugefügt: (24, 2), (10, 3), (5, 5), (4, 6), (3, 10) und (2, 18). Stephen Wolfram berichtet von einer (2, 5)-UTM^[10].

Kolmogorov-Komplexität[ Oben]

Kolmogorov, Chaitin und Solomonoff entwickelten unabhängig voneinander die Idee, die Komplexität einer Zeichenkette auf der Grundlage ihrer Komprimierbarkeit darzustellen, indem sie sie als Programm repräsentieren.

Gegeben sei eine universelle Turing-Maschine U. Der algorithmische Informationsgehalt, auch als algorithmische Komplexität oder Kolmogorov Komplexität (KC) H(X) der Zeichenkette X, ist definiert als die Länge des kürzesten Programms p auf U, das die Zeichenkette X erzeugt. Das kürzeste Programm, das eine Zeichenkette erzeugen kann, wird als elegantes Programm bezeichnet. Das Programm kann auch als X^* bezeichnet werden, wobei U(X^*) = X gilt, und kann selbst als Zeichenkette betrachtet werden. Gegeben ein elegantes Programm X^*,

H(X) = |X^*|

wo |X^*| die Größe von X^* ist.

Die Terminologie in der Literatur variiert. Zum Beispiel verwenden einige Autoren C_M(X) oder I(X) für H(X) auf Maschine M, oder I(X) für H(X), oder min(p) für |X^*|.

Ein String X wird als algorithmisch zufällig bezeichnet, wenn sein elegantes Programm X^* nicht kürzer ausgedrückt werden kann als X; das heißt, wenn seine algorithmische Komplexität maximal ist. Mit anderen Worten, es kann auf der Referenz-UTM nicht komprimiert werden.

Ein unendlich langer algorithmisch zufälliger String enthält keine redundanten Daten. Es lässt sich zeigen, dass der Anteil jedes Symbols im String ungefähr gleich ist und eine zufällige Verteilung aufweist. Wenn ein solcher String eine Zahl zwischen 0 und 1 (das Einheitsintervall) darstellt, dann ist die Zahl eine normale Zahl oder Borel-normale Zahl nach der Arbeit von Émile Borel.

Nicht alle normalen Zahlen sind algorithmisch zufällig. Eine Zahl kann normal sein, aber als ein kurzes Programm auf einer bestimmten UTM definiert sein. Ebenso sind nicht alle algorithmisch zufälligen Zahlen normal. Endlich lange Zeichenfolgen gelten per Definition als algorithmisch zufällig. Jede endlich lange Zeichenfolge kann als rationale Zahl in einer bestimmten Basis betrachtet werden, und rationale Zahlen können in keiner Basis normal sein.

Einige Punkte müssen bezüglich der Kolmogorov-Komplexität gemacht werden:

1. KC kann nicht berechnet werden. Wenn wir testen, ob ein Programm p die Zeichenfolge X auf U erzeugt, können wir niemals wissen, ob p anhalten wird (wie Turing zeigte). Selbst wenn wir ein Programm p₁ gefunden haben, das X auf U erzeugt, können wir nicht wissen, ob es ein kürzeres Programm p₀ gibt, das X auf U erzeugt. Man kann Schranken für KC abschätzen, aber die absolute Berechnung von KC für eine Zeichenfolge ist theoretisch unmöglich.
   
   
2. KC hängt von der ausgewählten Referenz-UTM ab, nicht nur von der Zeichenfolge. Wenn Sie zwei UTMs U und V haben, muss die Länge des kürzesten Programms p_U, das X auf U erzeugt, nicht der Länge des kürzesten Programms p_V entsprechen, das X auf V erzeugt. Mit anderen Worten, H_U(X) ist im Allgemeinen nicht gleich H_V(X). Normalerweise ist das nicht wichtig, weil die Referenz-UTM gegeben ist und alle Diskussionen relativ dazu stattfinden, oder weil implizit angenommen wird, dass jede ausgewählte UTM im Vergleich zu den sehr langen algorithmisch zufälligen Zeichenfolgen, über die gesprochen wird, nur einen kleinen Overhead hat. Das ist wichtig, wenn Sie keine Referenz-UTM haben und Sie nicht über sehr lange algorithmisch zufällige Zeichenfolgen sprechen (siehe unten unter Auswahl der UTM).
   
   
3. Es muss algorithmisch zufällige Zeichenfolgen geben. Dies ist eine Konsequenz des Schubfachprinzips. Es gibt 2ⁿ Zeichenfolgen der Länge n und 2ⁿ-1 Programme der Länge weniger als n. Es gibt einfach nicht genug kürzere Programme, um alle 2ⁿ Zeichenfolgen der Länge n zu erzeugen.
   
   
4. Die meisten Zeichenfolgen sind mindestens algorithmisch zufällig nahe. Dies ist eine weitere Konsequenz des Schubfachprinzips. Es gibt 2^n-k-1 Programme der Länge weniger als n-k und 2ⁿ - (2^n-k) = 2ⁿ(1-2^-k) Programme der Länge zwischen n-k und n. Setzen wir k = 10. Mindestens 99,9% der Zeichenfolgen der Länge n haben einen KC von mindestens n-10..
   
   
5. KC ist durch die Zeichenlängen plus eine Konstante begrenzt. Ein sehr einfaches Programm ist print X. Sein Overhead auf einer gegebenen UTM ist eine Konstante c. Der KC für eine beliebige Zeichenfolge auf dieser UTM kann die Länge der Zeichenfolge + c nicht überschreiten. Die Konstante hängt von der UTM ab.
   
   
6. Invarianz-Theorem. Wenn wir eine UTM U und eine andere TM V haben, gilt H_U(X) ≤H_V(X) + c für alle X. Die Konstante c hängt von U und V ab, aber nicht von X.
   
   
7. Algorithmisch zufällig ist nicht dasselbe wie statistisch zufällig. Wir betrachten Münzwürfe, Würfeln und radioaktiven Zerfall als nicht-deterministische oder stochastische Prozesse und nennen diese zufällig. Algorithmisch zufällig hat eine andere Definition und ist ein anderes Konzept, obwohl sehr lange algorithmisch zufällige Zeichenfolgen Symbolverteilungen mit statistischen Eigenschaften haben. Algorithmisch zufällige Zeichenfolgen sind entweder berechenbar und deterministisch oder unberechenbar.
   
   
8. KC ist nicht dasselbe wie Rechenkomplexität. Rechenkomplexitätstheorie befasst sich mit der Menge an Rechenressourcen (Zeit und Speicher), die benötigt wird, um ein Problem zu lösen. Rechenkomplexität steht in keinem Zusammenhang damit, ob eine Zeichenfolge auf einer gegebenen UTM komprimierbar ist.

Einige andere Konzepte [Oben]

Gemeinsame Information Inhalt. Angenommen, wir hätten eine UTM mit zwei Arbeitstapeten statt einer. Ein Programm könnte zwei Strings erzeugen, jeweils auf einer Arbeitstape. Alternativ könnte es zwei Strings auf einer Arbeitstape nacheinander erzeugen (möglicherweise durch einen Leerzeichen getrennt). Oder wir könnten dasselbe Programm auf zwei verschiedenen UTMs ausführen, die parallel laufen. Auf jeden Fall haben wir ein Programm, das zwei Strings erzeugt. Der gemeinsame Informationsgehalt H(X,Y) der Strings X und Y ist die Größe des kleinsten Programms, das sowohl X als auch Y gleichzeitig erzeugt.

Bedingter Informationsgehalt. Der bedingte oder relative Informationsgehalt H(X|Y) ist die Größe des kleinsten Programms, um X aus einem minimalen Programm für Y zu erzeugen. Beachten Sie, dass H(X|Y) Y^* und nicht Y benötigt. Chaitin zeigte, dass:

H(X,Y) ≤ H(X) + H(Y|X) + O(1)

wo O(1) eine Konstante darstellt, die den Rechenaufwand repräsentiert.

Gemeinsamer Informationsgehalt. Der gemeinsame Informationsgehalt H(X : Y) wird durch eine der folgenden Methoden berechnet:

H(X : Y) = H(X) + H(Y) - H(X,Y)

H(X : Y) = H(X) - H(X|Y) + O(1)

H(X : Y) = H(Y) - H(Y|X) + O(1)

Strings X und Y sind algorithmisch unabhängig, wenn

H(X,Y) ≈ H(X) + H(Y)

in diesem Fall ist der gegenseitige Informationsgehalt gering.

Es muss betont werden, dass, trotz einer Ähnlichkeit in Notation und Form zur klassischen Informationstheorie, die algorithmische Informationstheorie sich mit einzelnen Strings befasst, während die klassische Informationstheorie sich mit dem statistischen Verhalten von Informationsquellen befasst. Man kann einen Zusammenhang zwischen der mittleren Kolmogorov-Komplexität und der Shannon-Entropie herstellen, aber nicht zwischen KC und der Shannon-Entropie.

Programme und sich selbst delimitierende Codes [Oben]

Eine Aufgabe, die wir für unsere UTM U lösen müssen, besteht darin, festzustellen, wie man den Unterschied zwischen u, der Darstellung einer Turing-Maschine, und p, dem Programm, das die Zeichenkette X erzeugt, erkennt. Eine Methode, dies zu tun, besteht darin, u durch einen selbstbegrenzenden Code darzustellen. Ein Beispiel hierfür ist der unäre Code, in dem die Zahl N durch N-1 Nullen, gefolgt von einer einzelnen 1, dargestellt wird. Mit anderen Worten: 1 = 1, 2 = 01, 3 = 001, 4 = 0001 und so weiter. Der unäre Code ist ineffizient, wenn es viele große Zahlen gibt, kann aber in einigen Fällen eine gute Wahl sein.

Ein weiteres Beispiel ist das Hinzufügen eines Symbols zum Symbolsatz, dessen Bedeutung Ende ist. Wenn u als eine Binärzahl dargestellt wird, benötigen wir für das abgegrenzte u einen dreisymboligen Satz. Die Codes 0101101001e und 01011e können unterschieden werden, obwohl 01011 wie der Anfang von 0101101001 aussieht.

Ähnlich können wir, wenn wir ein Symbolsystem durch einen Binärcode (wie ASCII) darstellen, eine binäre Darstellung des Ende-Symbols (wie das ASCII EOF-Symbol) reservieren. Der einfachste Fall besteht darin, eine 2-Bit-Sequenz zu verwenden, die die beiden Binärsymbole 0 und 1 sowie das Ende-Symbol darstellt (00 = 0, 11 = 1, 01 = Ende).

Selbstbegrenzende Codes werden manchmal als Präfixcodes bezeichnet, da kein Code ein Präfix eines anderen Codes ist.

Auswahl von UTM [Oben]

Erinnern Sie sich daran, dass die Kolmogorov-Komplexität (die Länge des kürzesten Programms auf einer UTM, um eine Zeichenfolge zu berechnen) von der Auswahl der UTM abhängt. In der Algorithmischen Informationstheorie ist dies in der Regel unerheblich. Denken Sie daran, dass die obere Grenze der KC für eine Zeichenfolge durch eine Konstante c begrenzt ist, die den Overhead darstellt, um eine TM darzustellen, die "drucken X" auf der Referenz-UTM implementiert. Solange wir eine Referenz-UTM wählen, für die dieser Overhead im Vergleich zur Länge der bearbeiteten Zeichenfolgen sehr klein ist, können wir die Konstante ignorieren. Zum Beispiel können wir c ignorieren, wenn wir mit |X| > 1 Million arbeiten und c < hundert ist.

Alternativ, wenn alle Diskussionen sich auf eine gegebene Referenz-UTM beziehen, dann stellt c einen festen Offset zu unserer oberen Grenze dar, und für viele Arten theoretischer Diskussionen können wir ihn weglassen.

Im Allgemeinen können wir die Konstante nicht ignorieren, wenn wir nicht eines der unendlich vielen UTM als Referenz ausgewählt haben. Nichts zwingt uns, ein UTM zu verwenden, für das c klein ist. Mit anderen Worten, es existieren UTMs, auf denen "drucken X" nicht effizient codiert werden kann.

Das folgende Diagramm veranschaulicht das Problem, das sich auf den Schubfachprinzip bezieht. Nehmen wir an, wir haben drei verschiedene UTMs, U, V und W, die alle die Menge der möglichen Programme {up} auf die Menge der möglichen endlichen Zeichenfolgen {X} abbilden. Da wir uns nur mit der Länge der Eingabezeichenfolge beschäftigen, ist uns der Unterschied in den TM-Beschreibern bei U, V und W gleichgültig.

Abb. 2. Der Schubfachprinzip für verschiedene UTM

Für die Menge der Eingabezeichenfolgen, bei der |up| < n, muss jede UTM dank des Schubfachprinzips höchstens 2ⁿ Zeichenfolgen in {X} abbilden. Die Zielbereiche in {X} für U, V und W können sich überschneiden oder auch nicht. Sie müssen es nicht. Da wir über eine unendliche Anzahl von UTMs zur Auswahl verfügen, können wir uns vorstellen, dass jede Abbildung möglich ist, und dies kann tatsächlich dargestellt werden.

Zunächst betrachten wir folgende Art von Turing-Maschine: Sie liest ein Eingabeprogramm p als Zahl, die ihre Zustands­tabelle verwendet, um eine Sequenz zu beginnen. Jeder Schritt in der Sequenz gibt ein Symbol aus, ohne weitere Bezugnahme auf das Programm­band oder das Arbeitsband, und beendet sich dann. Dies implementiert eine Tabellen­abfrage. Wenn die TM N verschiedene Zahlen liest, kann sie N verschiedene Zeichenfolgen beliebiger Länge ausgeben. Wir könnten eine TM bauen, die Zeichenfolgen ausgibt, nachdem sie 2-Bit-Programme gelesen hat, wie folgt:

Die kleinste Tabelle ist natürlich eine Tabelle mit einem Eintrag, sodass wir mit diesem Typ von Turing-Maschine jede Zeichenfolge mit einem Programm von 1 Bit Länge ausgeben können.

Es gibt wirklich kein Limit für die Länge der Ausgabezeichenfolge einer Lookup-Tabelle TM. Wir benötigen einfach nur eine ausreichend große Tabelle, was uns zum folgenden Problem führt: Die Größe der Lookup-Tabelle übersteigt ihre längste Zeichenfolge. Mit anderen Worten, wir würden im Allgemeinen erwarten, dass die Zeichenfolge, die benötigt wird, um die TM zu beschreiben, viel länger ist als jede Zeichenfolge, die sie erzeugen kann. Genau dort wird die Auswahl der UTM kritisch.

Die Frage ist, wie wir die Auswahl des TM codieren, das auf der UTM ausgeführt werden soll. Da die Beschreibung unseres TM auf der UTM eine Zeichenkette ist, ist sie auch eine Zahl. Die UTM führt TM 1, TM 2, TM 3, … TM N usw. aus, je nachdem, welche Zahl in die UTM geladen wird. Wir können eine UTM so entwerfen, dass sie beim Lesen des TM-Beschreibers u fast überall in ihrer Zustands­tabelle springt, sodass jede Abbildung von u auf das implementierte TM möglich ist. Tatsächlich könnten wir erneut die Tabellen­suche verwenden.

Wir entwerfen eine UTM namens MFTM, oder „Meine Lieblingsturingmaschine". MFTM verfügt über eine unterteilte Zustands- und Aktionstabelle. Der erste Teil ist einer einzigen eingebauten Implementierung einer TM gewidmet, welche immer auch immer unsere Favorit sein mag. Der andere Teil implementiert jede andere beliebig gewählte UTM Z. MFTM liest die Eingabezeichenkette <a><q>. Wenn a eine 0 ist, führt es q auf der eingebauten TM aus. Wenn a ein anderes Symbol ist, führt es <q> = <z><p> auf Z aus, wobei z eine Beschreibung einer TM auf Z ist und p ein Programm.

Wenn wir in MFTM eine Tabelle-Look-up TM einbauen, kann sie beliebige Sequenzen aus sehr kurzen Eingaben erzeugen. Das kürzeste Programm auf MFTM wäre 2 Bits, wenn wir eine Tabelle mit einem Eintrag einbetten. MFTM verletzt das Schubfachprinzip nicht, weil jedes <u><p> auf Z auf MFTM um 1 Bit verlängert werden muss. Die KC (Kolmogorov-Komplexität) aller Strings, die nicht in die Tabelle eingebaut sind, steigt um 1 Bit.

Nun ist dies zwar ein zugegebenerweise schlauberiger Weg, um für jede beliebige Zeichenkette eine niedrige Kolmogorov-Komplexität zu erhalten, doch er veranschaulicht das Problem. Da es eine unendliche Anzahl von UTMs gibt und eine unendliche Anzahl von Möglichkeiten, TM-Beschreibungen auf UTMs zu kodieren, einschließlich selbstbegrenzender Codes, bei denen einige Beschreibungen von Natur aus kurz sind, existieren UTMs, für die beliebige Mengen endlicher Zeichenketten nicht algorithmisch zufällig sind. Dies ist wichtig, weil es zeigt, wie stark die KC von der Auswahl der UTM abhängen kann. Die Beschreibung der UTM wird nicht in die Berechnung der KC einbezogen.

Es ist auch möglich, eine UTM zu entwerfen, auf der Strings eine beliebig große KC aufweisen. Wir werden eine UTM namens RIM, oder Really Inefficient Machine, entwerfen. Sie wird einen selbstbegrenzenden Code verwenden, um TMs zu beschreiben, und dieser Code wird die schlechteste Effizienz aufweisen, die wir erfinden können. Anstatt 0 als 00, 1 als 11 und end als 01 zu codieren, werden wir 0 als eine aufeinanderfolgende Zeichenkette von n 0ern, 1 als eine aufeinanderfolgende Zeichenkette von n 1ern und end als jeden anderen Teilstring der Länge n codieren. Wir können n sehr groß machen, wie 10²⁰. Obwohl wir T möglicherweise als u mit q Bits codieren, kann RIM T nicht in weniger als nq Bits laden. Das bedeutet, dass nq eine untere Schranke für KC auf RIM ist.

Dies ist eine schlaue Methode, um für jede beliebige Zeichenkette eine hohe Kolmogorov-Komplexität zu erzielen, aber sie illustriert erneut das Problem. RIM verletzt nicht die Obergrenze für die KC oder den Invarianzsatz, da wir die Konstante c sehr groß werden lassen können. Tatsächlich haben wir dies künstlich getan.

Chaitins Haltewahrscheinlichkeit: Ω(Omega)[Top]

Chaitin erweiterte die Arbeit von Turing, indem er die Haltewahrscheinlichkeit definierte. Betrachtet man Programme auf einer universellen Turing-Maschine U, die keine Eingabe benötigen, so definieren wir P als die Menge aller Programme auf U, die anhalten. Sei |p| die Länge der Bitstring-Kodierung des Programms p, wobei p ein beliebiges Element von P ist. Die Haltewahrscheinlichkeit oder die Ω-Zahl wird wie folgt definiert:

Ω= ∑2^-|p| über alle p-Elemente von P

Wie bereits erwähnt, bezeichnet die absolute Wertnotation |p| die Größe oder Länge des Bitstrings p.

Man kann sich Ω so vorstellen, dass, wenn man eine UTM mit einer zufälligen Binärzeichenkette speist, die von einem Bernoulli-1/2-Prozess (wie dem Werfen einer fairen Münze) generiert wurde, Ω die Wahrscheinlichkeit ist, dass die UTM anhält.

Als Wahrscheinlichkeit hat Ω einen Wert zwischen 0 und 1. Chaitin zeigte, dass Ω nicht nur irrational und transzendent ist, sondern auch eine unentscheidbare reelle Zahl. Sie ist algorithmisch irreduzibel oder algorithmisch zufällig, egal welche UTM man wählt. Es gibt keinen Algorithmus, der ihre Ziffern berechnen kann.

Referenzen[Oben]

[Oben]