Folgen natürlicher Zahlen
Rechenvorschriften und Algorithmen
Rekursiven Funktionen
Turingmaschine und Berechenbarkeit
Die Liste aller berechenbaren Funktionen
Ewige Programmschleifen finden
Das Halteproblem
Nicht berechenbare Funktionen
Definieren ist nicht Berechnen
Das Halteproblem ist unlösbar
Gedanken zu Cantors Diagonalverfahren
Warum ist das Halteproblem unlösbar?
Schlussbemerkung
Bisher haben wir uns viel mit formalen axiomatisierten Systemen beschäftigt.
Dabei haben wir uns besonders für ein formales System interessiert,
von dem wir hoffen, dass es die Arithmetik der natürlichen Zahlen
umfasst. Ein solches System könnten wir dann als Fundament verwenden,
auf dem sich möglicherweise die gesamte Mathematik aufbauen ließe – so Hilberts Vision
aus dem Jahr 1900.
In diesem Unterkapitel werden wir uns den natürlichen Zahlen von einer anderen Seite her zuwenden. Wir interessieren uns für den Begriff der Berechenbarkeit. Den Zusammenhang zwischen diesem Begriff und formalen Systemen werden wir dann im nächsten Unterkapitel herstellen.
Wir wollen uns nicht auf das Berechnen bzw. Erzeugen einzelner natürlicher Zahlen beschränken. Interessanter wird es, wenn wir die Unendlichkeit ins Spiel bringen. Wir interessieren uns also nicht nur für einzelne natürliche Zahlen, sondern für ganze Listen solcher Zahlen, wobei die Liste unendlich lang sein darf. Man bezeichnet solche Listen auch als natürliche Zahlenfolgen. Hier ein Beispiel für eine solche Liste:
2, 4, 6, 8, 10, 12, ...
Ist diese Liste berechenbar, d.h. können wir die einzelnen Zahlen in dieser Folge eine nach der anderen angeben, so weit wie wir wollen? Die Antwort ist in diesem Fall einfach: ja, die Liste ist erzeugbar, denn man kann eine einfache Rechenvorschrift angeben: Der \(n\)-te Eintrag ist gleich dem Doppelten von \(n\). Bezeichnen wir den \(n\)-ten Eintrag als \( f(n) \), so lautet die Rechenvorschrift also \( f(n) = 2 n \), d.h. \( f(1) = 2, \; f(2) = 4 \) usw..
Die Notation \( f(n) \) ist naheliegend, wenn man sich vorstellt, dass der Wert \( f(n) \) durch die Anwendung einer mathematischen Funktion \(f\) auf die natürliche Zahl \(n\) erzeugt wird. Der Begriff Funktion bedeutet dabei soviel wie Zuordnung oder Abbildung. Mit \(f\) bezeichnen wir also eine Zuordnung, die jeder natürlichen Zahl \(n\) (für die \(f\) definiert ist) eine natürliche Zahl \(f(n)\) zuordnet. Man kann auch sagen, \(f\) definiert die Zahlenfolge. Dabei sind zwei Funktionen \(f\) und \(g\) genau dann gleich, wenn sie dieselbe Zahlenfolge definieren, also wenn \( f(n) = g(n) \) ist für alle natürlichen Zahlen \(n\), für die die Funktionen \(f\) und \(g\) definiert sind.
Es ist wichtig, zwischen den Begriffen Rechenvorschrift und Funktion sauber zu unterscheiden. Es gibt viele Möglichkeiten, eine Funktion zu definieren. Diese Definition kann gleichzeitig eine Rechenvorschrift beinhalten (z.B. \( f(n) = 2 n \) ), muss es aber nicht. Wir werden unten ein Beispiel kennenlernen, bei dem die Definition einer Funktion keine allgemeine Rechenvorschrift für alle Werte von \(f(n)\) enthält.
Im obige Beispiel ist der Wert von \(f(n)\) für jedes \(n\) definiert. Solche Funktion wollen wir als überall definierte Funktionen bezeichnen. Es ist aber auch der Fall denkbar, dass eine Funktion nicht überall definiert ist. Ein einfaches Beispiel ist die Division der Zahl 100 durch die Zahl \( (n-1) \) ohne Rest (d.h. Zahlen hinter dem Dezimalkomma werden abgeschnitten). Für \(n = 1 \) wäre das eine Division durch Null, d.h. \(f(n)\) ist bei \(n = 1 \) nicht definiert. Einen nicht definierten Wert in der Zahlenfolge wollen wir einfach durch eine Lücke darstellen. Die Zahlenfolge lautet dann
, 100, 50, 33, 25, 20, ...
d.h. die erste Zahl vor dem ersten Komma wird einfach nicht angegeben. Funktionen dieser Art wollen wir als partiell definierte Funktionen bezeichnen.
Überlegen wir uns nun genauer, was wir unter einer Rechenvorschrift verstehen wollen (statt Rechenvorschrift werden wir auch oft synomym den Begriff Algorithmus oder Computerprogramm verwenden).
In der Schule lernen wir beispielsweise, wie man mit Bleistift und Papier schrittweise eine komplizierte Multiplikation oder Division durchführt. Versuchen Sie einmal, mit Papier und Bleistift schriftlich die Division 627462 geteilt durch 3 durchzuführen, und Sie haben eine gute Vorstellung von einer Rechenvorschrift. Sie werden beginnen: Wie oft passt 3 in die erste Ziffer 6 hinein: einmal? – geht; zweimal? – geht; dreimal – zuviel!; also: zweimal. Sie schreiben eine 2 hin usw., so wie man das in der Schule gelernt hat. Auf diese Weise erzeugen Sie Schritt für Schritt die einzelnen Dezimalstellen des Ergebnisses. Da die Rechnung aufgeht, hören Sie bei der letzten Ziffer auf und sind fertig.
Versuchen Sie dann, mit demselben Verfahren und ohne Nachzudenken die Division 627462 geteilt durch 0 (Null) durchzuführen. Sie werden sagen: durch Null kann man doch nicht dividieren! Doch halt: Sie sollen mechanisch wie bei der Division durch 3 rechnen, ohne Nachzudenken. Also beginnen Sie: Wie oft passt 0 in die erste Ziffer 6 hinein: einmal? – geht; zweimal? – geht; ... . Wenn Sie nach diesem Schema vorgehen, bleiben Sie in einer endlosen Schleife hängen, denn "zuviel" wird nie erreicht. Das Verfahren wird also für die Division durch Null nie ein Ergebnis liefern, und das ist auch gut so, denn wir wissen ja, dass der Wert von 627462 / 0 gar nicht definiert ist.
Damit haben wir bereits eine intuitive Vorstellung davon, was eine Rechenvorschrift ist: sie ist ein mechanisches Verfahren, das dem Durchführen von schriftlichen Rechnungen mit Papier und Bleistift entspricht. Dabei erwarten wir, dass eine Rechenvorschrift zu einer Funktion \(f\) für jede vorgegebene natürliche Zahl \(n\), für die die Funktion definiert ist, den Wert \(f(n)\) nach endlich vielen Schritten erzeugt.
Was aber, wenn die Funktion für den Wert \(n\) nicht definiert ist? In diesem Fall fordern wir, dass die Rechenvorschrift für dieses \(n\) ewig weiterläuft, ohne jemals einen Wert für dieses \(n\) auszugeben. Die Rechenvorschrift würde beim Abarbeiten der Rechenschritte in eine ewige Schleife (Loop) geraten. Programmierern ist ein solches Verhalten von Computerprogrammen gut bekannt.
Im Prinzip ist noch der Fall denkbar, dass eine Rechenvorschrift keine Zahl erzeugt, sondern beispielsweise eine Zeichenkette aus Buchstaben und dann anhält. Wir könnten in diesem Fall die Rechenvorschrift leicht modifizieren: Statt anzuhalten könnte die Zeichenkette durch eine kleine Zusatz-Rechenvorschrift in eine natürliche Zahl umgewandelt werden, worauf der Algorithmus anhält. Beispielsweise könnte jeder Buchstabe durch eine natürliche Zahl codiert werden (man denke an den bekannten ASCII-Code bei Computern). Wir wollen diesen Fall nicht weiter beachten: entweder die entsprechenden Rechenvorschriften werden so modifiziert, dass sie eine Zahl ausgeben und dann wie zuvor anhalten, oder sie werden von vorne herein gar nicht erst berücksichtigt – schließlich lassen sich diese Rechenvorschriften immer in endlich vielen Schritten erkennen, da sie anhalten.
Man kann generell die Definition des Begriffs Rechenvorschrift auf verschiedene Arten präzisieren.
Eine Möglichkeit sind die rekursiven Funktionen. Schauen wir uns dazu noch einmal die beiden Axiome der Addition aus Kapitel 2.1 an:
Dabei ist \( n^* \) wieder der Nachfolger von \(n\) (beispielsweise ist 1 der Nachfolger von 0).
Funktionieren diese Axiome? Angenommen, wir wollen zu der Zahl 5 die Zahl 2 hinzuaddieren. Sagen uns die beiden Axiome, wie das geht?
Setzen wir \(n = 5 \) und \( m = 0 \) in das zweite Axiom ein: \begin{equation} 5 + 0^* = (5 + 0)^* \end{equation} Aus dem ersten Axiom wissen wir: \( 5 + 0 = 5 \). Das können wir auf der rechten Seite einsetzen und erhalten \begin{equation} 5 + 0^* = 5^* \end{equation}
Nun zum nächsten Schritt: was ist \( 5 + 0^{**} \), wobei \( 0^{**} \) der Nachfolger des Nachfolgers von \( 0 \) ist? Setzen wir \( m = 0^{**} \) in das zweite Axiom ein: \( 5 + 0^{**} = (5 + 0^*)^* \). Die Klammer auf der rechten Seite haben wir bereits im vorherigen Schritt ermittelt: es war \( 5 + 0^* = 5^* \) . Damit ergibt sich \( 5 + 0^{**} = 5^{**} \). Übersetzt in die übliche Schreibweise bedeutet dieses Ergebnis: \( 5 + 2 = 7 \).
Die beiden Axiome haben es also erlaubt, durch zweifache Anwendung des zweiten Axioms den Wert von \( 5 + 2 \) zu berechnen. Dabei wurde das zweite Axiom einmal auf sein eigenes Zwischenergebnis angewendet – daher der Begriff rekursiv. Allgemein liefern die beiden Axiome auf diese Weise eine rekursive Definition der Addition beliebiger natürlicher Zahlen unter Verwendung der Nachfolger-Funktion (gekennzeichnet durch den hochgestellten Stern).
Dieser kurze Ausflug vermittelt einen Eindruck davon, wie mit Hilfe rekursiver Funktionen eine Rechenvorschrift zusammengebaut werden kann. Das soll uns an dieser Stelle erst einmal genügen.
Eine andere Möglichkeit, den Begriff Rechenvorschrift zu präzisieren, wurde von Alan Turing im Jahr 1936 in seiner berühmten Arbeit On computable numbers, with an application to the Entscheidungsproblem veröffentlicht. Turing erdachte eine Maschine, die in der Lage ist, auf sehr einfache Weise Berechnungen durchzuführen (Computer wie wir sie heute kennen gab es damals noch nicht). Ihm zu Ehren bezeichnet man sie heute als Turingmaschine. Wir sind im Vorwort bereits auf die Funktionsweise dieser Maschine eingegangen. Rufen wir uns die Details noch einmal kurz ins Gedächtnis:
Eine Turingmaschine besteht aus einem endlosen Band, auf dem Zeichen eines vorgegebenen Zeichensatzes aufgedruckt sein können (inclusive Leerzeichen), und einem Lese-Schreibkopf, der über einem dieser Zeichen auf dem Band positioniert ist. Das Band entspricht dem Arbeitsspeicher (RAM) der Maschine und dient gleichzeitig als Ein- und Ausgabemedium. Der Lese-Schreibkopf kann nun in einem Verarbeitungsschritt das jeweilige Zeichen vom Band lesen, es durch ein anderes ersetzen sowie einen Schritt nach links oder rechts auf dem Band rücken. Zudem verfügt die Turingmaschine über Programmzeilen (Turing sprach von inneren Zuständen), zwischen denen sie wechseln kann. Diese Programmzeilen legen fest, wie die Turingmaschine auf das vom Band gelesene Zeichen reagieren soll, und in welche Programmzeile sie für den nächsten Verarbeitungsschritt springen soll.
Turing definierte nun eine Rechenvorschrift einfach als etwas, das sich auf einer Turingmaschine ausführen lässt. Eine Rechenvorschrift entspricht also einem Programm für die Turingmaschine (ein Beispiel folgt weiter unten).
Nun könnte man meinen, dass dadurch der Begriff der Rechenvorschrift viel zu eng gefasst würde. Schließlich ist die Turingmaschine sehr einfach gebaut. Vermutlich gibt es doch komplizierte Rechenoperationen, die eine Turingmaschine gar nicht ausführen kann!?
Doch dieser Eindruck täuscht. Bisher konnte man zeigen, dass alles, was man intuitiv als Rechenvorschrift bezeichnen würde, auch auf einer Turingmaschine ausgeführt werden kann. Auch verschiedene andere Definitionen des Begriffs Rechenvorschrift erwiesen sich als gleichwertig zu der von Alan Turing.
Die Turingmaschine ist im Grunde ein sehr einfacher Computer. Mit ihr gelang es Turing, zu präzisieren, was mit dem mechanischen Ausführen einer Rechnung gemeint ist. Man kann zeigen, dass alles, was auf einem modernen Digitalcomputer ausgeführt werden kann, auch auf einer Turingmaschine ausführbar ist. Daher ist es gerechtfertigt, sich Rechenvorschriften auch als Computerprogramme oder als Programme für die Turingmaschine vorzustellen.
Aufgrund dieser Erfahrungen hat man die folgende These formuliert, die als Church'sche These bezeichnet wird:
Alle bisherigen Erfahrungen haben diese These bestätigt. Dennoch handelt es sich um eine These, die durch zukünftige Entwicklungen in Frage gestellt werden könnte. Für die folgende Diskussion wollen wir jedoch die Church'sche These akzeptieren.
Mit Hilfe des Begriffs Rechenvorschrift können wir nun definieren, was wir unter einer berechenbaren Funktion verstehen wollen:
Dass die Rechenvorschrift an den Stellen, an denen \(f\) nicht definiert ist, ewig weiterläuft und nicht stattdessen so etwas wie ERROR ausgibt, macht Sinn, denn wir wissen ja vielleicht gar nicht, wann und ob die Rechnung zum Ziel gelangt. Die Rechenmaschine soll also nicht zu früh aufgeben und hilflos ERROR ausdrucken, sondern tapfer immer weiterrechnen, so wie es die Rechenvorschrift vorschreibt. Nur wenn das für bestimmte Eingabewerte \( n \) ewig so weitergeht, sagen wir, dass die berechenbare Funktion dort nicht definiert ist.
Wenn es berechenbare Funktionen gibt, existieren dann auch nicht-berechenbare Funktionen? Die Idee erscheint zunächst absurd: wie soll man denn eine Funktion überhaupt definieren, ohne zugleich eine Rechenvorschrift mit anzugeben, die die Funktion erst festlegt? In der Tat: es erscheint unmöglich, eine nicht-berechenbare Funktion konkret anzugeben. Aber das bedeutet nicht, dass solche Funktionen nicht im Prinzip denkbar wären.
Versuchen wir, uns dem Problem zu nähern, indem wir versuchen, eine Liste aller berechenbaren arithmetischen Funktionen aufzustellen, die natürliche Zahlen als Input und Output haben. Die Liste darf dabei unendlich lang sein, und wir wollen Duplikate erlauben, d.h. die Funktionen dürfen auch mehrfach in der Liste vorkommen (denn zu einer berechenbaren Funktion kann es mehrere Rechenvorschriften geben, und wir wollen die Liste mithilfe einer Liste aller existierenden Rechenvorschriften erstellen).
Mathematisch ordnet die Liste jeder berechenbaren Funktion eine oder mehrere natürliche Zahlen zu, nämlich die Zeilennummern, in denen sie steht. Ein Verfahren, mit dem wir diese Liste aufstellen können, ist also letztlich ein Algorithmus, mit dem sich jeder berechenbaren Funktion in endlich vielen Schritten eine oder mehrere natürliche Zahlen zuordnen lassen, wobei eine solche Zahl immer nur zu einer Funktion gehört (in jeder Listenzeile darf ja nur eine Funktion stehen).
Das Aufstellen einer solchen Liste aller berechenbaren Funktionen würde natürlich unendlich viele Schritte erfordern, denn es gibt unendlich viele berechenbaren Funktionen. Aber wenn man eine bestimmte Funktion \(f\) in der Liste sucht, so muss man sie nach endlich vielen Schritten dort finden, wenn man die Liste von oben nach unten durchsucht. Man weiß zwar nicht, wie lange man suchen muss, aber man weiß, dass man sie irgendwann findet, denn sie muss ja irgendwo in der Liste stehen. Das ist mit einer unendlich langen Liste aller berechenbaren Funktionen gemeint.
Stellen wir uns die Rechenvorschrift einer berechenbaren Funktion als (endliches) Computerprogramm vor. Letztlich wird jedes Computerprogramm als eine Folge von Nullen und Einsen auf der Festplatte des Rechners abgelegt. Diese Folge von Nullen und Einsen kann man auch als die Binärdarstellung einer natürlichen Zahl interpretieren. Eine Liste aller natürlichen Zahlen in Binärdarstellung enthält also alle Computerprogramme. Man kann aus dieser Liste nun alle Zahlen (Binärstrings) weglöschen, die kein Computerprogramm sind, d.h. die der betrachtete Computer nicht versteht (wir setzen voraus, dass das möglich ist). Und schließlich behalten wir nur diejenigen Programme in der Liste, die eine Eingabemöglichkeit für eine natürliche Zahl \(n\) haben. Übrig bleibt die Liste aller Programme für die Berechnung von Funktionen einer natürlichen Zahl (sollten Buchstaben ausgegeben werden, so wandeln wir sie wie gehabt mit Hilfe einer Codierungstabelle in Zahlen um). Dabei verlangen wir nicht, dass das Programm für jeden Eingabewert \(n\) anhält. Tut es das nicht, so ist der entsprechende Funktionswert \(f(n)\) für das eingegebene \(n\) nicht definiert. Also gilt:
Das überzeugendste und sauberste Argument für die Existenz dieser Liste
erhält man über die Turingmaschine:
Nach unserer Definition muss sich jede Rechenvorschrift auf einer Turingmaschine umsetzen lassen,
d.h. zu jeder Rechenvorschrift gehört ein spezielles Turing-Programm.
Ein solches Turing-Programm ist sehr einfach gebaut.
Betrachten wir ein Beispiel: nehmen wir an, die Turingmaschine kann nur die Zeichen
'0', '1' und 'B' (für Blank, also das Leerzeichen) vom Band lesen und auf das Band schreiben
(man kann zeigen, dass es egal ist, welchen Zeichensatz man auswählt; die entsprechenden
Turingprogramme lassen sich ineinander umwandeln).
Dann könnte man ein Turing-Programm beispielsweise so aufschreiben:
Wie ist dieses Programm zu lesen?
Das erste der 4 durch Kommata getrennten Zeichen gibt den Programmblock an, in dem sich das Turing-Programm gerade befindet. Man spricht auch von dem inneren "Zustand" der Turingmaschine.
Das zweite Zeichen entspricht einer Wenn-Dann-Bedingung: Wenn das vom Band gelesene Zeichen gleich 0 (oder 1 oder B) ist, dann ... .
Das dritte Zeichen sagt, was die Turingmaschine tun soll. Sie hat fünf Aktionen zur Auswahl:
Das vierte Zeichen gibt an, in welchen Programmblock die Maschine wechseln soll, um den nächsten Verarbeitungsschritt auszuführen.
Damit können wir jede Programmzeile in eine lesbare Form überführen. Die erste Zeile sagt also: Block 0: Wenn Du eine "0" vom Band gelesen hast, gehe auf dem Band einen Schritt nach rechts und bleibe in Programmblock 0..
Das obige Programm dient dazu, eine 1 zu einer vorgegebenen Zahl in Binärschreibweise hinzuzuaddieren. Diese Zahl steht dabei in Binärform auf dem Band, z.B. 11001 (dies wäre die Zahl 25). Ansonsten enthält das Band nur Leerzeichen. Das Programm startet in Programmblock 0 mit dem Lese-Schreibkopf ganz links auf dem ersten Zeichen, das zur Zahl gehört (man sagt, das Programm startet in der Standardkonfiguration). Am Schluss steht das Ergebnis in Binärschreibweise auf dem Band, wobei der Lese-Schreibkopf sich wieder links auf dem ersten Zeichen der Ergebniszahl befindet (man sagt, das Programm stoppt in der Standardkonfiguration).
Probieren Sie es an einem Beispiel mal aus! Sie werden sehen, dass Block 0 nur dazu dient, den Kopf zu Beginn der Rechnung rechts auf das letzte Zeichen der Zahl zu bewegen. Block 2 dagegen fährt am Schluss der Rechnung den Kopf nach links auf das erste Zeichen des Ergebnisses und stoppt (d.h. springt zum nicht existierenden Block 4). Die eigentliche Rechnung erledigen Block 1 und 3.
Allgemein besteht ein Turingprogramm aus endlich vielen Strings (Zeichenketten) der Form q, S, A, q' , die wir auch hintereinanderschreiben und durch Semikolon (;) trennen können, so dass ein großer zusammengesetzter String entsteht (ganz analog zu den Beweisketten aus dem letzten Unterkapitel). Unser obiges Turingprogramm ist in dieser Schreibweise durch den folgenden String gegeben:
0, 0, R, 0; 0, 1, R, 0; 0, B, L, 1; 1, 0, 1, 2; 1, 1, 0, 3; 1, B, 1, 4; 2, 0, L, 2; 2, 1, L, 2; 2, B, R, 4; 3, 0, L, 1;
Wir können genau sagen, wann ein solcher zusammengesetzter String wohlgeformt ist:
Man kann die auf diese Weise zusammengesetzten Strings nun der Größe nach aufsteigend in einer Liste anordnen und die endlich vielen Strings der gleichen Größe dabei z.B. alphabetisch sortieren. Wir sind im letzten Kapitel bereits ausführlich darauf eingegangen und wollen dies hier nicht wiederholen. Damit haben wir:
Wir können nun jedes dieser Turingprogramme auf die Berechnung eines Funktionswertes \(f(n)\) loslassen. Dazu geben wir diese natürliche Zahl \(n\) auf dem Band in Binärform vor und starten die Turingmaschine in Standardkonfiguration, also in Programmblock 0 mit dem Lese-Schreibkopf ganz links auf dem ersten Zeichen, das zur Zahl \(n\) gehört. Wenn das Programm anhält, überprüfen wir, ob genau ein Binärstring auf dem Band steht, und ob der Lese-Schreib-Kopf sich wieder links auf dem ersten Zeichen dieses Strings befindet, d.h. ob die Turingmaschine in Standardkonfiguration anhält. Wenn das der Fall ist, dann ist der auf dem Band stehende Binärstring der gesuchte Ergebniswert \(f(n)\). Hält die Turingmaschine zwar an, aber nicht in Standardkonfiguration, so werten wir das beispielsweise so, als ob der Ausgabewert \( f(n) = 0 \) erzeugt worden wäre (die Turingprogramme ließen sich leicht entsprechend abändern). Bleibt noch der Fall, dass die Turingmaschine überhaupt nicht stoppt. Dann sagen wir, der Ergebniswert \( f(n) \) ist nicht definiert.
Es ist also nicht notwendig, bestimmte Turingprogramme aus dieser Liste aller Turingprogramme auszusortieren. Wir können jedes Turingprogramm aus der Liste auf einen Binärstring loslassen, der die vorgegebene natürliche Zahl \(n\) darstellt, und das Ergebnis als Berechnung des Funktionswertes \(f(n)\) interpretieren. Jedes Turingprogramm entspricht also einer berechenbaren Funktion \(f\), wobei es durchaus mehrere Turingprogramme für eine Funktion \(f\) geben darf. Die Liste der Turingprogramme ergibt damit eine Liste der berechenbaren Funktionen von natürlichen Zahlen, wobei Funktionen auch mehrfach in der Liste auftauchen dürfen. Dabei ist es wichtig, dass wir nicht nur überall definierte Funktionen betrachtet haben, sondern auch partiell definierte Funktionen in der Liste zulassen, denn sonst müssten wir uns dem Problem stellen, die nur partiell definierten Funktionen zu identifizieren und aus der Liste herauszulöschen – und ob das möglich ist, wissen wir momentan noch nicht. Tatsächlich werden die meisten Turingprogramme die triviale Funktion berechnen, bei der \(f(n)\) für keinen Wert von \(n\) definiert ist. Aber das soll uns nicht stören, denn wir wollen ja zunächst überlegen, was prinzipiell möglich ist und noch wichtiger: was prinzipiell unmöglich ist.
Halten wir unser Ergebnis noch einmal fest:
Wie oben erwähnt, enthält diese Liste sehr viele Zeilen, in denen das Turingprogramm nur für wenige oder für gar kein \(n\) eine natürliche Zahl als Ergebnis ausgibt und dann anhält. Die zu diesen Zeilen gehörenden Funktionen \(f\) sind also nur partiell oder sogar nirgends definiert. Es wäre sicher interessant, diese Zeilen aus der Liste zu streichen und nur die Zeilen zu behalten, bei denen das entsprechende Turing-Programm für jedes auf dem Band vorgegebene \(n\) einen Funktionswert \(f(n)\) berechnet. Übrig bliebe eine Liste aller berechenbaren überall definierten Funktionen von natürlichen Zahlen.
Können wir also die Zeilen mit den nur partiell definierten Funktionen aus der Liste streichen? Dazu müssen wir die partiell definierten von den überall definierten Funktionen unterscheiden können, denn nur so lassen sich die zu streichenden Zeilen in der Liste identifizieren.
Nun haben wir oben ja klar gesagt, wann eine berechenbare Funktion für ein vorgegebenes \(n\) nicht definiert ist: das entsprechende Turingprogramm (also die zur Funktion gehörende Rechenvorschrift) stoppt niemals und läuft ewig weiter.
Woher aber wissen wir, ob eine Turingmaschine ewig weiterlaufen wird? Was ist, wenn die Turnigmaschine bereits seit 5 Wochen läuft, ohne aufzuhören? Wird Sie gleich stoppen, oder vielleicht morgen, oder in 10 Jahren, oder aber nie?
Ausprobieren kann diese Frage nicht klären, denn wir können nie sicher sein, dass die Turingmaschine ewig weiterlaufen wird: sie könnte ja gleich stoppen und ihr Ergebnis präsentieren. Wir müssen uns also nach einer anderen Lösung für das Problem umsehen.
Betrachten wir das folgende sehr einfache Turingprogramm:
Block 0 sagt: egal, was auf dem Band ist, schreibe eine 1 auf das Band und gehe zu Block 1. Block 1 liest dann diese 1, lässt sie unverändert und geht wieder zu Block 0. Wir sehen sofort: das geht ewig so weiter. Die Maschine springt in einer unendlichen Schleife zwischen Block 0 und Block 1 hin und her. Hier könnten wir ewig warten – die Maschine wird nie anhalten.
Überlegen wir, was wir gerade getan haben: Wir haben das Turingprogramm analysiert und sind zu dem Schluss gekommen, dass es eine ewige Schleife enthält. Deshalb sind wir sicher, dass es niemals anhält.
Gibt es eine allgemeine mechanische Vorgehensweise (einen Algorithmus), mit der sich solche Schleifen in jedem Turingprogramm aufspüren lassen? Nun, wir könnten nach zwei Programmblöcken suchen, die sich gegenseitig immer wieder aufrufen. So etwas lässt sich sicher als Algorithmus formulieren. Aber Schleifen können auch viel komplizierter sein: drei Programmblöcke können sich zirkulär gegenseitig aufrufen, oder vier, oder 789245 Blöcke ... . Erfahrene Computerprogrammierer wissen, wie schwierig es ist, in großen komplizierten Programmen, die Millionen von Programmzeilen umfassen können, solche unendlichen Schleifen zu finden. Nur mit großer Disziplin lässt sich halbwegs der Überblick behalten, und man kann nie sicher sein, ob das Programm nicht doch in irgendwelchen Situationen in eine unendliche Schleife gerät.
Es ist also intuitiv nicht klar, ob wir einen Algorithmus formulieren können, der beliebig große Turingprogramme erfolgreich auf Schleifen hin analysieren kann und uns somit sagt, ob es anhält oder nicht.
Nehmen wir einmal an, es gäbe einen solchen Algorithmus. Genauer: Nehmen wir an, es gäbe einen Algorithmus, mit dem man entscheiden kann, ob das Turingprogramm einer berechenbaren Funktion \(f\) für alle Eingabewerte \(n\) anhält, oder ob es irgendeinen Eingabewert \(n\) gibt, bei dem es nicht anhält. Dann könnten wir in der unendlich langen Liste der berechenbaren Funktionen die überall definierten von den nur partiell definierten Funktionen unterscheiden. Wir könnten schrittweise alle nur partiell definierten Funktionen aus der Liste entfernen. Das Ergebnis wäre die (unendlich lange) Liste aller überall definierten berechenbaren Funktionen einer natürlichen Variable (wir haben gerade eine Algorithmus angegeben, mit dem sie sich erzeugen lässt).
Wir wollen die erste Funktion in dieser Liste (wenn es die Liste denn gibt) mit \( f_1 \) bezeichnen, die zweite mit \( f_2 \) usw.. Dann können wir eine Tabelle aller Funktionswerte aufstellen:
Die erste Zeile enthält alle Funktionswerte von \( f_1 \), die zweite von \( f_2 \) usw.. Dies wäre dann eine unendlich lange Liste aller (ebenfalls z.T. unendlich langen) berechenbaren natürlichen Zahlenfolgen, die keine Lücken (d.h. nicht definierte Funktionswerte) enthalten.
Mit Hilfe der obigen Tabelle können wir nun eine besondere Zahlenfolge konstruieren. Dazu gehen wir in der Tabelle die Diagonale von links oben nach rechts unten entlang, nehmen das jeweilige Diagonalelement \( f_1(1) , f_2(2) \) usw. und verändern diese Zahl indem wir beispielsweise eine Eins dazu addieren. Diese Folge natürlicher Zahlen sieht also so aus:
Nennen wir die entsprechende Funktion \( f_D \) (das \(D\) steht für Diagonale, da wir die neue Funktion mit Hilfe der Diagonalelemente der obigen Tabelle konstruiert haben). Es ist also \begin{equation} f_D(n) = f_n(n) + 1 \end{equation} d.h. der n-te Funktionswert der neuen Diagonal-Funktion \( f_D \) ist gleich dem n-ten Diagonalelement der Tabelle plus Eins.
Man bezeichnet dieses Konstruktionsverfahren als Cantor'sches Diagonalverfahren. Es spielt eine zentrale Rolle bei der Untersuchung der allgemeinen Grundlagen von Mathematik und Informatik. Der berühmte Mathematiker Georg Cantor benutzte dieses Verfahren im Jahr 1873, um zu beweisen, dass es keine vollständige Liste der reellen Zahlen geben kann.
Nun war aber nach unserer Annahme unsere obige algorithmisch erzeugte Liste aller natürlichen Zahlenfolgen vollständig, d.h. auch die neue Zahlenfolge, die sich mit der Funktion \( f_D \) erzeugen lässt, muss in ihr enthalten sein. In der ersten Zeile kann sie aber nicht stehen, denn \( f_D(1) \) ist nach Konstruktion um eins größer als das erste Folgenelement \( f_1(1) \), d.h. die beiden Funktionen unterscheiden sich mindestens für den Input \( n = 1 \). In der zweiten Zeile kann die neue Folge ebenfalls nicht stehen, denn \( f_D(2) \) ist um eins größer als \( f_2(2) \) usw.. Wir haben die neue Folge gerade so konstruiert, dass sie in der Liste nicht enthalten sein kann, denn sie weicht garantiert zumindest im Diagonalelement von jeder der Folgen in der Liste ab.
Damit haben wir also eine neue, berechenbare, überall definierte Funktion bzw. Zahlenfolge konstruiert, die nicht in der oben erzeugten Liste aller berechenbaren, überall definierten Funktionen (bzw. den daraus berechneten Zahlenfolgen) enthalten ist. Diese Liste kann also – entgegegen unserer Annahme – nicht durch einen Algorithmus erzeugbar sein, obwohl sie unendlich viele Einträge enthält.
Nun könnten wir natürlich die neue Funktion der Liste hinzufügen. Doch dann können wir das Diagonalverfahren erneut durchführen und eine weitere Funktion konstruieren, die nicht in der Liste enthalten ist. Das Loch kann nicht gestopft werden!
Fassen wir unser Ergebnis noch einmal zusammen:
Wenn es aber keine algorithmisch erzeugbare vollständige Liste aller berechenbaren, überall definierten Funktionen einer natürlichen Variablen gibt, dann kann es auch keinen Algorithmus geben, mit dem man allgemein entscheiden kann, ob das Turingprogramm einer berechenbaren Funktion \(f\) für alle Eingabewerte \(n\) anhält, oder ob es irgendeinen Eingabewert \(n\) gibt, bei dem es nicht anhält (ansonsten hätten wir ja sofort einen Algorithmus zur Erzeugung der Liste gefunden). Und weil es diesen Algorithmus nicht gibt, können wir in der unendlich langen Liste aller berechenbaren Funktionen \( f(n) \) die überall definierten nicht von den nur partiell definierten Funktionen unterscheiden. Die nur partiell definierten Funktionen können wir nicht per Algorithmus aus der Liste entfernen, und die Liste aller überall definierten berechenbaren Funktionen lässt sich nicht erzeugen. Wir fassen zusammen:
Noch eine kurze Bemerkung:
Die Aussage "es gibt keine vollständige (unendlich lange) Liste
aller berechenbaren, überall definierten Funktionen einer natürlichen Variablen"
ist falsch, wenn man diese Aussage so versteht, dass diese Funktionen
mathematisch nicht abzählbar seien (in einer früheren Version dieses Kapitels hatte ich hier einen
Fehler gemacht, auf den mich ein aufmerksamer Leser hinwies – nochmal vielen Dank!).
Richtig ist, dass es keinen Algorithmus gibt, um diese Liste aufzustellen und
so diese Funktionen durchzunummerieren. Dennoch kann mathematisch eine
eindeutige Zuordnung zwischen den natürlichen Zahlen (oder zumindest einer Untermenge dieser Zahlen)
und den berechenbaren, überall definierten Funktionen definiert werden, d.h.
diese Funktionen sind in diesem Sinn abzählbar. Diese Zuordnung ist einfach aufgrund der Liste
aller berechenbaren (nicht unbedingt überall definierten) Funktionen gegeben, denn
jede Funktion hat in dieser Liste eine eindeutige Nummer; also haben auch die
in dieser Liste enthaltenen überall definierten Funktionen eine eindeutige Nummer.
Das Problem ist, dass man nicht immer weiß, ob in einer Zeile eine
überall definierte Funktion steht.
Wenn aber die berechenbaren, überall definierten Funktionen in diesem Sinn abzählbar sind, warum führt dann Cantors Diagonalverfahren nicht zu einem Widerspruch? Nun, ein Algorithmus zur Durchführung von Cantors Diagonalverfahren setzt voraus, dass man die Liste der berechenbaren, überall definiertenFunktionen wirklich schrittweise ausgeben kann (da die Liste unendlich lang ist, wird man natürlich nie fertig; man kann aber sicher sein, dass jede Zeile irgendwann drankommt). Da das aber nicht geht, gibt es auch keinen Algorithmus für Cantors Diagonalverfahren in diesem Fall. Die oben definierte Funktion \( f_D \) ist also zwar mathematisch definierbar, aber nicht berechenbar und muss deswegen auch gar nicht in der Liste aller berechenbaren, überall definierten Funktionen enthalten sein. Damit entfällt auch der Widerspruch. Man sieht, wie subtil die Argumentation hier bisweilen ist, und wie sehr man aufpassen muss, um nicht irgendeine Unachtsamkeit zu begehen!
Kommen wir zurück auf eine Frage, die wir bei der Definition der berechenbaren Funktionen bereits gestellt hatten: Gibt es auch nicht-berechenbare Funktionen natürlicher Zahlen? Das wären Funktionen, bei denen es keine Rechenvorschrift gibt, die für jede natürliche Zahl \(n\), für die die Funktion \(f\) definiert ist, in endlich vielen Schritten den Wert \( f(n) \) ausgibt, und die für jede natürliche Zahl \(n\), für die die Funktion \(f\) nicht definiert ist, ewig weiterläuft.
Nun haben wir mit \( f_D \) gerade ein Beispiel für eine nicht berechenbare Funktion kennengelernt. Wir wollen uns noch ein weiteres Beispiel ansehen, das sich durch eine leichte Abwandlung von Cantors Diagonalmethode erzeugen lässt.
Wir wissen (siehe oben), dass sich die berechenbaren Funktionen durchnummerieren lassen. Es gibt eine vollständige Liste der berechenbaren Funktionen. Wie oben können wir daher eine Tabelle der Funktionswerte aufstellen:
Diesmal sind wir aber sicher, dass es diese Liste gibt, denn auch die nur partiell definierten Funktionen sind in der Liste enthalten. Analog zu vorher definieren wir nun eine neue Funktion \( f_D \) über die Diagonalelemente dieser Tabelle. Wenn das n-te Diagonalelement \(f_n(n) \) definiert ist, so addieren wir eine Eins hinzu, um den Wert \(f_D(n) = f_n(n) + 1 \) zu definieren. Ist das Diagonalelement dagegen nicht definiert, so soll einfach \(f_D(n) = 1 \) sein.
Diese Funktion ist wieder so konstruiert, dass sie nicht in der Liste enthalten ist, denn sie unterscheidet sich von jeder in der Liste aufgeführten Funktion \( f_n \). Also kann diese Funktion nicht berechenbar sein, denn sonst müsste sie in der vollständigen Liste aller berechenbaren Funktionen enthalten sein, was sie aber nicht ist (so ist sie ja konstruiert). Also gilt:
Doch warum die obige Funktion nicht berechenbar? Schließlich haben wir sie oben explizit definiert! Ist diese Definition nicht auch gleichzeitig eine Rechenvorschrift?
Sie kann es nicht sein, denn wir haben ja gerade gezeigt, dass die obige Funktion nicht berechenbar ist. Doch wo ist das Problem? Versuchen wir also, \( f_D(n) \) mit Hilfe der obigen Definition zu berechnen. Dazu starten wir die Rechenvorschrift (das Turingprogramm) zur Berechnung des Diagonalelementes \( f_n \). Wenn die Rechnung stoppt, addieren wir Eins zu dem Ergebnis und sind fertig. Was aber, wenn die Rechnung einfach nicht stoppt? Ist \( f_n \) dann definiert oder nicht? Warten allein löst das Problem nicht, denn die Rechnung könnte ja morgen stoppen und ein Ergebnis liefern. Oder aber sie stoppt nie. Man bezeichnet die Fragestellung, ob die Berechnung des Funktionswertes einer beliebig vorgegebenen Funktion \( f_n \) für das Argument \(n\) anhält, als Turings Halteproblem.
Gäbe es eine allgemeine Methode, mit der man der Rechenvorschrift (dem Turingprogramm) zu einer Funktion immer ansehen könnte, ob sie irgendwann stoppt, dann wäre die Funktion \( f_D(n) \) berechenbar. Aber wir haben gezeigt, dass \( f_D(n) \) nicht berechenbar ist. Also gibt es keinen allgemeinen Algorithmus zur Lösung von Turings Halteproblem. Wir könnten bis in alle Ewigkeit dasitzen und darauf warten, dass die Berechnung von \( f_n(n) \) endlich zu einem Ende kommt. Und solange die Rechnung noch läuft, können wir den Wert von \( f_D(n) \) nicht angeben, denn wir können nicht ausschließen, dass morgen das Ergebnis doch noch ermittelt wird. Computerbesitzer kennen das Problem: wenn der Computer nicht antwortet, so könnte er in eine Endlosschleife geraten sein, oder aber er ist gerade nur sehr beschäftigt und wird sie in einer Minute (oder einer Stunde ?!) wieder beachten. Fassen wir zusammen:
An dieser Stelle entsteht oft ein Missverständnis: Im Einzelfall kann man eventuell schon herausfinden, ob ein vorgegebenes Turingprogramm für einen bestimmten Eingabewert \(n\) anhält oder nicht. Es könnte gelingen, in dem Turingprogramm endlose Schleifen aufzuspüren, oder aber das Turingprogramm ist so übersichtlich, dass man sicher ist, dass keine solchen Schleifen existieren. Aber: es gibt keine allgemein anwendbare Methode, die in beliebig komplizierten Programmen alle nur denkbaren Loops finden kann.
Das bedeutet, dass man bei der oben definierten nicht berechenbaren Funktion für einzelne Eingabewerte \(n\) schon in der Lage ist, den Wert von \( f_D(n) \) zu berechnen: dann nämlich, wenn das Turingprogramm von \( f_n(n) \) nach einiger Zeit anhält, oder wenn man sicher ist, dass es nicht anhält. Aber irgendwann stößt man auf der Diagonale auf eine Funktion \( f_n \), deren Rechenvorschrift so kompliziert ist, dass alle bis dahin verwendeten Verfahren zu Suchen von Endlosschleifen in Turingprogrammen nicht mehr greifen.
Und so geht es immer weiter: jedes eingesetzte Schleifen-Suchverfahren (also jeder Versuch, Turings Halteproblem zu lösen) stößt irgendwann auf eine Rechenvorschrift, die zu komplex für das Suchverfahren ist. Man kann also schrittweise versuchen, immer mehr Werte der nicht berechenbaren Funktion \( f_D \) zu berechnen, benötigt dabei aber immer neue und aufwendigere Algorithmen (Schleifen-Suchverfahren), um zu bestimmen, ob die Berechnung des jeweiligen Diagonalelementes \( f_n(n) \) anhält oder nicht. Das ist mit nicht berechenbarer Funktion gemeint: es gibt keine Rechenvorschrift, mit der sich alle Funktionswerte an den Stellen \(n\), an denen die Funktion definiert ist, berechnen lassen. Jede Rechenvorschrift stößt bei dieser Funktion an ihre Grenzen, d.h. es gibt Eingabewerte \(n\), an denen die Rechenvorschrift den Funktionswert nicht ermitteln kann.
Es ist interessant, dass man solche nicht-berechenbaren Funktionen überhaupt definieren kann. Definieren ist also etwas Abstrakteres als Berechnen. Eine Definition kann Begriffe und Elemente enthalten, die sich einer konkreten Berechnung entziehen.
Die folgende Sichtweise macht diesen Unterschied deutlich: Definitionen bewegen sich in einer abstrakten Ideen-Welt (Plato hat diesen Begriff bereits in der Antike geprägt). Im Grunde bewegt sich die gesamte Mathematik in dieser Ideen-Welt. Sie arbeitet mit abstrakten Begriffen, Ideen und Strukturen, die letztlich versuchen, unsere intuitiven Gedanken über Zahlen, Mengen usw. zu präzisieren.
Rechenvorschriften bewegen sich dagegen in der konkreten, realen Welt. Sie lassen sich (zumindest im Prinzip) von Hand oder mit Computern durchführen.
Die Ursache für die Existenz nicht berechenbarer Funktionen liegt darin, dass wir bei deren Definition so tun, als ob die Aussage "die Rechenvorschrift hält nicht an" für beliebig komplizierte Rechenvorschriften eine objektive Tatsache ist. Jede Rechenvorschrift liegt ja vollständig vor, und damit ist genau festgelegt, wie der Rechenvorgang ablaufen wird. Aber um herauszufinden, ob eine Rechenvorschrift irgendwann anhält, genügt es nicht, sie einfach ablaufen zu lassen, denn man kann nicht ewig warten. Man muss die Rechenvorschrift analysieren, um Schleifen zu entdecken. Im Einzelfall kann diese Analyse Erfolg haben, doch es gibt keine allgemeine Methode (keinen Algorithmus, keine Rechenvorschrift), die bei allen denkbaren Rechenvorschriften diese Anaylse erfolgreich durchführen kann. Es ist damit Geschmackssache, ob man die Aussage "die Rechenvorschrift hält nicht an" für jede nur denkbare Rechenvorschrift als objektive Tatsache ansieht oder nicht. Es wird Rechenvorschriften geben, die so kompliziert sind, dass man diese Information mit den vorhandenen Werkzeugen einfach nicht ermitteln kann. Tut man im Sinne Platos dennoch so, als sei die Information an sich vorhanden, und verwendet sie bei der Definition von partiell definierten Funktionen, so liefert die Mathematik gleichsam als Quittung die Existenz nicht berechenbarer Funktionen.
Damit wird deutlich, dass Ideen-Welt und reale Welt nicht perfekt zusammenpassen. Es gibt immer wieder Überaschungen und unerwartete Nebenwirkungen, wenn wir versuchen, eine perfekte Ideen-Welt aufzubauen, indem wir intuitive mathematische Konzepte präzisieren. So sind der Begriff der Funktion einer natürlichen Variable und der Begriff der Rechenvorschrift nicht deckungsgleich, obwohl sie auf den gleichen intuitiven Konzepten beruhen. Analog ist die Idee der unendlichen Menge aller natürlichen Zahlenfolgen nicht deckungsgleich mit der Idee einer unendlich langen Liste. Es gibt in der Ideen-Welt verschiedene Unendlichkeiten . Und auch die Ideen-Welt ist nicht perfekt, wie wir noch sehen werden.
Es gibt noch einen anderen Beweis für die Unlösbarkeit von Turings Halteproblem, der mit dem obigen Beweis eng verwandt ist. Da dieser Beweis weit verbreitet ist, möchte ich ihn an dieser Stelle der Vollständigkeit halber kurz darstellen.
Wir beginnen wieder mit der vollständigen Liste aller berechenbaren Funktionen \( f_n \), wobei auch partiell definierte Funktionen in der Liste vorkommen. Nun definieren wir die folgende partiell definierte Funktion \(D\):
Die Konstruktion dieser Funktion ist sehr ähnlich zu der oben verwendeten Konstruktion. Wir wollen aber diesmal nicht wie oben direkt untersuchen, ob diese Funktion in der Liste aller berechenbaren Funktionen vorkommt, sondern wir erzeugen auf etwas andere Art einen Widerspruch (der natürlich dann ebenso zeigt, dass die Funktion nicht berechenbar ist und nicht in der Liste vorkommt).
Nehmen wir also an, Turings Halteproblem wäre lösbar, d.h. es gäbe eine Turingprogramm, dass alle Turingprogramme erfolgreich auf Endlosschleifen hin untersuchen kann. Dann ist die Funktion \(D\) berechenbar. Ein entsprechendes Programm würde schematisch in etwa so aussehen:
"Programm zur Berechnung der Funktion \(D\):
READ EINGABEWERT \(n\);
READ TURINGPROGRAMM \(n\);
hält_an = HALT (EINGABEWERT \(n\), TURINGPROGRAMM \(n\));
IF hält_an THEN
DO LOOP; "Endlosschleife
ELSE
PRINT 0;
ENDIF;
END;
Das Programm verwendet dabei die Funktion HALT (EINGABEWERT \(n\), TURINGPROGRAMM \(n\)), die bestimmt, ob das \(n\)-te Turingprogramm (vorliegend als lange Zeichenkette) bei Eingabewert \(n\) anhält oder nicht. Diese Funktion überprüft also das Turingprogramm auf Schleifen. Wenn Turings Halteproblem lösbar ist, so muss sich eine solche Funktion programmieren lassen.
Die berechenbare Funktion \(D\) muss dann in der obigen vollständigen Liste aller berechenbaren Funktionen irgendwo vorkommen – nennen wir diese Zeilennummer \(d\) (also \( D = f_d \) ). Das entsprechende Turingprogramm bezeichnen wir analog als TURINGPROGRAMM \(d\). Es ist das obige Programm, umformuliert als Turingprogramm.
Was geschieht nun, wenn wir das Programm auf sich selbst loslassen und \( D(d) \) (also \( f_d(d) \) ) bestimmen wollen?
Wir erhalten einen Widerspruch! Damit ist unsere Annahme falsch. Turings Halteproblem ist unlösbar. Die Funktion HALT (EINGABEWERT \(n\), TURINGPROGRAMM \(n\)) lässt sich nicht programmieren und damit auch nicht in obigem Programm verwenden. Die Funktion \(D(d)\) ist nicht berechenbar, d.h. ein Programm zu ihrer Berechnung gibt es nicht.
In den obigen Beweisen haben wir immer wieder über Listen und Diagonalelemente gesprochen. Der entscheidende Trick war immer wieder, die Diagonalelemente dazu zu verwenden, um eine neue Zeile zu konstruieren, die in der bisherigen Liste nicht vorhanden gewesen sein kann (Cantors Diagonalverfahren).
Sehen wir uns nochmal die Schritte an, die dazu notwendig sind:
Wenn sich Cantors Diagonalverfahren bei einer Liste von Objekten (Zahlenfolgen, reellen Zahlen, Programmen, beweisbaren Ausdrücken usw.) durchführen lässt, so ergeben sich folgende Möglichkeiten:
Die obigen Beweise für die Unlösbarkeit von Turings Halteproblem sind alle recht einfach und zwingend. Sie haben aber einen Nachteil: man weiß nicht so recht, woran es letztlich liegt, dass Turings Halteproblem unlösbar ist. Wo ist eigentlich die innere Ursache für diese Unlösbarkeit?
In Kapitel 3.4 (Chaitins Zufallszahl der Weisheit) werden wir auf diesen Punkt noch einmal im Detail zurückkommen. Die wesentlichen Ideen möchte ich aber auch hier schon mal andeuten:
Nehmen wir an, wir hätten Turings Halteproblem für alle Programme bis \(n\) Bit Programmlänge gelöst (dazu setzen wir irgendeine Programmiersprache voraus, bezüglich der wir die Programmlänge angeben können). Das Lösen des Halteproblems sollte hier kein Problem sein, denn die Zahl der Programme mit maximal \(n\) Bit Länge ist endlich. Zudem können wir uns ja erst einmal auf kurze Programme (also kleines \( n \) ) beschränken, sodass sich Schleifen in diesen Programmen gut aufspüren lassen.
Wir wollen hier nur Programme betrachten, die keinen Eingabewert benötigen. Das ist keine Beschränkung, denn wir können ja für jeden Eingabewert ein eigenes Programm schreiben, das in seinem Programmcode zugleich die Rechenvorschrift ( \(f\) genannt) und den Eingabewert (nennen wir ihn \(m\) im Unterschied zur Programmlänge \(n\)) enthält. Statt \(f(m)\) könnten wir \(f_m\) schreiben: das Programm \(f_m\) enthält die Rechenvorschrift \(f\) und den Eingabewert \(m\). Man kann sich vorstellen, dass das Programm erst den Wert \(m\) auf das Band schreibt und dann die Rechenvorschrift \(f\) darauf ansetzt. Da das Programm die Zahl \(m\) in ihrem Programmcode enthält, geht \(m\) auch in die Programmlänge ein: je größer \(m\) ist, umso länger ist \(f_m\) ( uff .... ist gar nicht so leicht, das einigermaßen präzise hinzuschreiben ... ).
Mit diesem Wissen schreiben wir nun ein Programm (nennen wir es \( \mathrm{HALT}_n \) ), das eine Liste aller anhaltenden Programme mit maximal \(n\) Bit Programmlänge ausgibt. Dabei soll \( \mathrm{HALT}_n \) nicht irgendein schlampig geschriebenes Programm sein, sondern es soll das kürzest mögliche Programm sein, das diese Liste ausgibt.
Wir schreiben nun ein Programm (nennen wir es \(P\) ), das unser Halteprogramm \( \mathrm{HALT}_n \) enthält und das folgenden Algorithmus ausführt (siehe auch Kapitel 3.4):
Programm \(P\):
Damit haben wir ein Programm \(P\) geschrieben, das irgendwann eine Zahl \(x\) ausgibt, die von keinem Programm mit maximal \(n\) Bit Länge ausgegeben werden kann. Dann aber muss das Programm \(P\) selbst mehr als \(n\) Bit lang sein. Wir notieren: \begin{equation} |P| > n \end{equation} wobei \( |P| \) die Programmlänge von \(P\) ist, also beispielsweise 5 MB oder 3 GB.
Wie lang ist nun das kürzeste Programm \(P\), das den obigen Algorithmus durchführt? Es besteht aus der obigen Schleife, die eine konstante Anzahl Bit benötigt, sowie aus dem Programm \( \mathrm{HALT}_n \). Also gilt für die Programmlängen: \begin{equation} |P| = |\mathrm{HALT}_n| + c \end{equation} wobei \(c\) eine konstante Zahl ist, die nicht von \(n\) abhängt. Zusammen mit der Tatsache, dass \(P\) länger als \(n\) Bit sein muss, folgt \begin{equation} n < |P| = |\mathrm{HALT}_n| + c \end{equation} oder anders geschrieben: \begin{equation} |\mathrm{HALT}_n| > n - c \end{equation} Wenn wir nun die maximale Programmlänge \(n\) der betrachteten Programme, für die das Halteproblem gelöst sein soll, immer größer werden lassen, so fällt \(c\) irgendwann kaum noch ins Gewicht. Wir sehen also, dass die Länge des Programm \( \mathrm{HALT}_n \), das alle anhaltenden Programme bis \(n\) Bit Länge ausgeben kann, mindestens proportional zur Maximallänge \(n\) dieser Programme anwächst. Die minimale Information, die wir über das Halteproblem hineinstecken müssen, wächst mindestens linear mit der Maximalgröße der betrachteten Programme.
Kann \( \mathrm{HALT}_n \) nun ein Programm sein, das nur die Zahl \(n\) als Konstante enthält, aber sich ansonsten nicht mit \(n\) ändert (also einen von \(n\) unabhängigen Algorithmus enthält)? Die Konstante \(n\) benötigt als Binärzahl höchstens \( \log_2 (n) \) Bit. Daher hätte dieses Programm eine Größe von \( \log_2 (n) + d \) Bit (wobei \(d\) eine Konstante ist). Für die Lösung des Halteproblems bis \(n\) Bit Programmlänge benötigt man aber mindestens \( n - c \) Bit, d.h. ein Programm, das einen festen Algorithmus und als Zusatzinformation nur die Zahl \(n\) enthält, kann nicht genügend Information beinhalten, um das Halteproblem bis \(n\) Bit Programmlänge zu lösen, denn dafür sind mindestens \( n - c \) Bit Information notwendig. Jeder Algorithmus ist also ab Programmen bestimmter Größe mit der Lösung des Halteproblems überfordert, denn er kann nicht die notwendige Informationsmenge beinhalten, die zur Lösung mindestens notwendig ist. Genau das ist der Grund für die Unlösbarkeit von Turings Halteproblem!
Die obige Diskussion ist natürlich nicht neu. Sie findet sich in verschiedener Form in vielen Texten über die Grundlagen von Mathematik und Informatik. Daher möchte ich noch eine leichte Abwandlung erwähnen, die man dort oft finden kann:
Statt der Berechnung von Funktionen einer natürlichen Variable wird die Berechnung von reellen Zahlen betrachtet. Eine reelle Zahl kann man als eine Dezimalzahl definieren, die unendlich viele Dezimalstellen hinter dem Dezimalkomma haben kann, wobei die Ziffern keinem allgemeinen Schema folgen müssen. Ein Beispiel für eine solche Dezimalzahl ist die Kreiszahl \( \pi = 3,1415926... \) . Statt die natürliche Zahlenfolge 3, 1, 4, 1, 5, 9, 2, 6, ... zu betrachten, kann man genauso gut die reelle Zahl \( \pi \) betrachten. Programme, die reelle Zahlen berechnen, können leicht so modifiziert werden, dass sie natürliche Zahlenfolgen (und damit Funktionen einer natürlichen Variable) berechnen und umgekehrt. Man muss einfach nur Kommas einfügen oder weglassen. Berechenbare (überall definierte) Funktionen entsprechen berechenbaren reellen Zahlen. Das Halteproblem ist dann die Frage, ob ein Programm zur Berechnung einer reellen Zahl die \(n\)-te Dezimalstelle dieser Zahl in endlicher Zeit ausgibt oder nicht. Cantors Diagonalverfahren beweist, dass es keine vollständige Liste aller reellen Zahlen gibt. Und schließlich wird es nicht-berechenbare reelle Zahlen geben.
Damit sind wir am Ende dieses sicher nicht einfachen Kapitels angekommen. Wir haben gesehen, was mechanische Rechenvorschriften, Computer und Algorithmen leisten können, und was sie nicht leisten können. Im nächsten Kapitel werden wir sehen, wie sich diese Ergebnisse auf Hilberts Vision einer kompletten Axiomatisierung der Mathematik auswirken.
© Jörg Resag, www.joerg-resag.de
last modified on 23 February 2023