Zufallsbit

Vielleicht erinnert sich noch jemand, dass ich in grauer Vorzeit mal eine Serie über Automatentheorie gestartet habe, mit dem Ziel, irgendwann zur Entscheidbarkeitstheorie zu gelangen. Der Grund, warum ich das nie weitergeführt habe ist, dass ich Automatentheorie nicht besonders spannend finde. Also überspringe ich den langweiligen Teil, komme direkt wieder zu Turingmaschinen und schreibe vielleicht später einen Beitrag über Automatentheorie mit einem eher zusammenfassenderen Charakter.

Entscheidbarkeitstheorie also. Die meisten Probleme sind ja irgendwie durch eine konkrete Fragestellung motiviert. Hier ist diese Frage, welche Funktionen entschieden werden können und welche nicht. Ich werde noch darauf kommen was das im Detail bedeutet. Erstmal führen wir eine neue Art Turingmaschine ein, die wir später brauchen.

Eine Turingmaschine, nennen wir sie M, ist ja folgendermaßen definiert:

Dabei ist Q die Menge der Zustände und q₀ identifiziert den Startzustand. ist das Bandalphabet und umfasst alle Buchstaben, die auf dem Band auftreten können. Dazu gehört insbesondere das "Blank" B, das nur als Platzhalter für "leer" steht. Für die bessere Lesbarkeit. ist das Eingabealphabet, was im wesentlichen mit dem Bandalphabet identisch ist, nur ohne das B. Außerdem können spezielle "Trennungssymbole" im Bandalphabet vorkommen, die man beim Entwurf des Algorithmus zur Vereinfachung verwenden kann. Genau wie man bei C++ Programmen vielleicht eine temporäre Variable zur Zwischenberechnung von Ergebnissen verwenden würde. Bleibt das , was die Zustandsübergangsfunktion darstellt. Wir erinnern uns: Eine Turingmaschine liest in jedem Schritt genau ein Zeichen, wechselt den Zustand, schreibt ein Zeichen zurück und bewegt den Kopf. Die Zustandsübergangsfunktion beschreibt, abhängig von gelesenen Zeichen und dem aktuellen Zustand, welche Aktionen passieren sollen. Oder anders gesagt: , wobei "0" für "keine Kopfbewegung" und -1 oder +1 für "links" bzw. "rechts" steht.

So eine gewöhnliche Turingmaschine hat einen gewaltigen Nachteil. Sie ist mit der formalen Definition bereits vollständig programmiert. Und zwar endgültig. Viel schöner und vertrauter wäre es doch, wenn eine Turingmaschine nur die "Hardware" zur Verfügung stellen würde und wir das Programm auf das Band schreiben könnten, genau wie wir das bei normalen Computern tun. Da schreiben wir das Programm auf die Festplatte (genauer gesagt in den Bootsektor) und von da aus guckt unser Computer nur, welches Programm an der richtigen Stelle der Festplatte zur Ausführung bereit liegt. Man stelle sich vor, wir würden für jeden auszuführenden Algorithmus einen neuen Prozessor kaufen und dem nur die Instanzen füttern. Ein Sortierprozessor zum Beispiel, dem wir nur Ganzzahlen zum Sortieren geben könnten, oder ein "Fülle-den-Cache-mit-Daten-Prozessor". Im echten Leben mutet das absurd an, aber so machen es klassische Turingmaschinen und für die Theorie kann man das auch tun.

Aber es geht eben auch anders, und das nennt man eine "universelle Turingmaschine", kurz UTM, noch kürzer U. Diese kann ein beliebiges Programm (bzw. eine andere, normale Turingmaschine M) ausführen. Die Eingabe besteht jetzt nicht mehr aus einem Wort w, sondern aus (<M>w). Dabei ist w nach wie vor das zu bearbeitende Wort, neu ist <M>, die so genannte Gödelnummer der zu simulierenden Turingmaschine M.

Man kann jede normale TM in eine lange Zahl codieren, die dann wiederum eindeutig ist. Zu jeder Gödelnummer gehört genau eine Turingmaschine. Diese Nummer wiederum gibt man dann als Eingabe an die UTM, die dann die zur Gödelnummer zugehörige TM simuliert. Diese Codierung funktioniert so:

, dann und Kopfbewegungen , dann

Keine Erklärung nötig soweit? Doch? Na gut. 

Zuerst transferieren wir das Bandalphabet (hier oBdA {0,1,B}) in . Jetzt gibt es also für jeden möglichen Bandbuchstaben ein entsprechendes X mit einem Index dran. Das gleiche passiert mit den Kopfbewegungen. Statt {-1,0+1} benutzen wir jetzt die Ds mit jeweils einem Index. Warum wir diese scheinbar sinnlose Transformation machen wird erst gleich klar, erstmal müssen wir uns einig sein, dass man den Zustandsübergang jetzt auch schreiben kann wie . Der Vorteil ist, dass jetzt alle Zustandsübergänge bis auf die Indizes gleich aussehen (bitte nochmal genau hinschauen wenn das nicht klar ist). Wenn man also wollte, könnte man die Übergänge also auch nur mit Zahlen aufschreiben.

Und das ist ja schließlich unser Ziel gewesen. Nun, die universelle TM hat allerdings auch nur ein {0,1} Alphabet, deshalb notiert man einen einzelnen Zustandsübergang so:

Jetzt dienen die Einsen als "Trenner" für eine Anzahl von Nullen, die mit dem ursprünglichen Zustandsübergang korrespondiert. Ein alter Übergang würde mit X₀=0, X₁=1 und D₁=-1 aussehen wie 001100001010. Wenn ich ab jetzt code(x) schreibe, meine ich abkürzend eine solche Zahl, einen Zustandsübergang repräsentierend.

Wo wir uns jetzt diese ganze Arbeit gemacht haben, können wir damit endlich wieder auf die Gödelnummer zurück kommen. Die sieht jetzt nämlich so aus:

111 code(1) 11 code(2) 11 ... 11 code(n-1) 11 code(n) 111

Drei Einsen markieren also Start und Ende der Gödelnummer, zwei Einsen trennen zwei Codierungen für die Übergänge. Das Ziel ist erreicht, die Turingmaschine wird in einer langen, langen Nummer notiert, die offensichtlich auch wieder in die entsprechende Maschine zurück rechnen lässt. Wenn wir jetzt eine solche Gödelnummer, zusammen mit dem zu entscheidenden Wort an die UTM übergeben, kann diese Schritt für Schritt die Gödelnummer lesen, den neuen Zustand (und damit die neue Position in der Gödelnummer) berechnen und am Ende entscheiden, ob das Wort akzeptiert wird oder nicht. Wie das genau funktioniert wollt ihr nicht wissen, die Gödelnummerkonstruktion war ja schon etwas unheimlich. Nur so viel: Man kann Turingmaschinen auch mit mehreren Speicherbändern definieren. Davon nehmen wir uns in diesem Fall drei, schreiben die zu simulierende Gödelnummer auf das erste, das Wort auf das zweite und auf das dritte kommt der aktuelle Zustand der zu simulierenden TM. Dann wird die Programmierung der UTM zwar weniger hässlich, aber nicht viel.

Bleibt die Frage nach der Rechenzeit. Wenn man sich die Rechenoperationen der UTM allerdings genau anschaut, wird schnell klar, dass die aufwändigste Operation die Suche nach der neuen Position in der Gödelnummer ist. Die UTM ist damit nur konstant langsamer als die ursprüngliche TM, hier droht also keine exponentielle Gefahr, außer die ursprüngliche TM war eh schon exponentiell langsam.

So weit, so gut. Wir haben gesehen, dass man eine TM auch als lange Nummer schreiben kann. Außerdem gibt es offensichtliche eine universelle Turingmaschine, die mit dieser Nummer und dem zu entscheidenden Wort diese TM simulieren kann. Benutzen kann man das für... ääh... eigentlich kann man das nicht benutzen. Man braucht es lediglich später für einen wichtigen Beweis. Ist theoretische Informatik nicht schön?

Wer hier aber dringend eine "Auflösung" braucht, der kann sich ja damit behelfen, dass die UTM offenbar eine praxisnähere Version von Turingmaschinen darstellt, denn man kann sie (auf aufwändige Art und weise) programmieren und muss sich nicht für jeden Algorithmus eine neue Turingmaschine kaufen. Gott sei dank.

Update: Übrigens..