Existenz nicht-berechenbarer Funktionen
Zielsetzung - Funktionen zählen
Es ist gar nicht so einfach, Funktionen zu konstruieren, die nicht berechenbar sind. Wir schlagen daher (vorerst) nicht den Weg ein, Funktionen konkret vorzustellen, die als nicht-berechenbar nachgewiesen werden können. Unser Weg soll (vorerst) darin bestehen, beliebige bzw. berechenbare Funktionen zu zählen. Wenn sich hier ein Unterschied ergibt, dann muss es nicht-berechenbare Funktionen geben. Die Schwierigkeit dieses Weges besteht darin, dass es unendlich viele (berechenbare) Funktionen gibt. Wir müssen daher einen kleinen Exkurs in das Zählen unendlicher Mengen machen.
Abzählbarkeit und Überabzählbarkeit
Mathematiker nennen eine Menge M abzählbar, wenn die Elemente von M durchnummeriert werden können. Alle Elemente aus M müssen bei der Nummerierung erfasst werden. Wiederholungen sind dabei zugelassen. Formal lässt sich diese Eigenschaft von Mengen so beschreiben.
Eine Menge M heißt abzählbar genau dann, wenn es eine Nummerierungsabbildung i von der Menge der natürlichen Zahlen in die Menge M gibt, bei der alle Elemente aus M als Bildelemente natürlicher Zahlen erfasst werden.
Eine Menge M heißt überabzählbar genau dann, wenn sie nicht abzählbar ist.
Beispiel: Die Menge der geraden Zahlen ist abzählbar. Die folgende Auflistung liefert implizit eine mögliche Nummerierung.
0, 2, 4, 6, ...
Beispiel: Die Menge der ganzen Zahlen ist abzählbar. Die folgende Auflistung liefert implizit eine mögliche Nummerierung.
0, 1, -1, 2, -2, 3, -3, ...
Abzählbarkeit der Menge aller berechenbarer Funktionen
Im letzten Abschnitt ist bereits der folgende fundamentale Sachverhalt über Turingmaschinen gezeigt worden.
Satz (über die Abzählbarkeit von Turingmaschinen)
Die Menge aller Turingmaschinen über dem Eingabealphabet {I} und dem Bandalphabet {I, B} ist abzählbar.
Beachte, dass im letzten Abschnitt sogar mehr gezeigt wurde. Es wurde dort gezeigt, dass die Zuordnung Turingmaschine - Nummer in beide Richtungen berechnet werden kann.
Aus einer nummerierten Auflistung aller Turingmaschinen gewinnt man sofort eine nummerierte Auflistung aller Turingmaschinen-berechenbaren Funktionen: In einem ersten Schritt streicht man alle Turingmaschinen in der Auflistung, die keine Funktion berechnen. In einem zweiten Schritt bestimmt man aus den Turingmaschinen die jeweils berechneten Funktionen. Beachte, dass nicht gefordert ist, dass diese Schritte algorithmisch durchgeführt werden müssen.
Satz (über die Abzählbarkeit von Turingmaschinen-berechenbaren Funktionen)
Die Menge aller Turingmaschinen-berechenbaren Funktionen von N nach N ist abzählbar.
Wir wenden uns jetzt der Menge aller (partiellen) Funktionen von N nach N zu.
Überabzählbarkeit der Menge aller Funktionen
Angenommen, die Menge aller (partiellen) Funktionen von N nach N ist abzählbar.
Dann gibt es eine nummerierte Auflistung, mit der alle diese Funktionen erfasst werden:
f0, f1, f2, f3, f4, ...
Jede dieser Funktionen ordnet allen natürlichen Zahlen eine natürliche Zahl oder den Wert u (für undefiniert) zu. Eine Zuordnungstabelle für alle Funktionen der Auflistung könnte z.B. so aussehen:
Wir konstruieren jetzt eine weitere Funktion f von N nach N nach dem folgenden Schema:
Wir benutzen also die Funktionswerte in der Diagonalen der Ausgangstabelle und ändern sie alle systematisch ab.
Die Funktion f ist so definiert, dass sie sich an mindestens einer Stelle von jeder Funktion der Auflistung f0, f1, f2, f3, f4, ... unterscheidet.
Damit sind wir aber an einem Punkt angelangt, an dem wir uns in Widersprüche verwickeln. Wir sind von der Annahme ausgegangen, dass die Menge aller (partiellen) Funktionen von N nach N abzählbar ist. Aus einer möglichen Abzählung (in Form einer nummerierten Auflistung) haben wir eine Funktion f von N nach N konstruiert. Diese Funktion f muss Element der Menge M sein (da sie ja eine Funktion von N nach N ist) und gleichzeitig unterscheidet sie sich von allen Elementen von M (an mindestens einer Stelle). So etwas ist unmöglich. Die einzige Möglichkeit, aus diesem Dilemma herauszukommen, ist die Folgerung, dass wir von einer falschen Annahme ausgegangen sind.
Satz (über die Überabzählbarkeit der Menge aller Funktionen)
Die Menge aller (partiellen) Funktionen von N nach N ist überabzählbar.
Existenz nicht-berechenbarer Funktionen
Aus den gewonnenen Abzählbarkeitsaussagen ergibt sich direkt der folgende zentrale Satz.
Satz (über die Existenz nicht-berechenbarer Funktionen)
Es gibt (partielle) Funktionen von N nach N, die nicht Turingmaschinen-berechenbar sind.
Das Ergebnis ist interessant und gleichzeitig ein wenig unbefriedigend. Wir wissen jetzt, dass es Funktionen geben muss, die nicht Turingmaschinen-berechenbar sind, allerdings kennen wir noch keine einzige. In den weiteren Kapiteln lernen wir solche Funktionen kennen.
