Zufallsbit

Obwohl ich im Moment echt durch den Wind bin, fühle ich irgendwie die Verpflichtung, hier auch mal wieder etwas substantielles zu schreiben, auch wenn es wahrscheinlich weniger umfangreich wird als sonst.

Es geht mal wieder um das Halteproblem, heute machen wir einen weiteren (und letzten) Zwischenschritt, um danach endlich das Halteproblem anzugehen.

Zunächst brauchen wir dafür die so genannte kanonische Ordnung. Das ist eine spezielle Sortierung von Bitstrings (also eine Ordnung auf {0,1}*). Dabei steht ein Wort w vor einem anderen Wort w', wenn:

1)  |w| < |w'|

oder 2) |w| = |w'| und w steht lexikographisch vor w'

Anders gesagt wird zuerst nach Länge des Wortes, dann erst nach lexikographisch Ordnung sortiert. Kürzeste Worte kommen also zuerst, inklusive dem leeren Wort: , 0, 1, 00, 01, 10, 11, 000, 001...

Jetzt überlegen wir uns eine Matrix, wobei die Zeilen mit Turingmaschinen und die Spalten mit allen möglichen Eingabewörtern in kanonischer Ordnung gefüllt werden. Das sieht bis jetzt so aus:

Die Matrix ist natürlich unendlich, denn sowohl die Anzahl der Wörter als auch die Menge der Gödelnummern hört nie auf. Jetzt kommt an eine Schnittstelle von Turingmaschine und Wort jeweils eine 0 oder eine 1, je nachdem ob die Turingmaschine das Wort akzeptiert oder nicht.

In diesem Fall würde die Turingmaschine die Wörter {w2,w4,w5,...} akzeptieren und {w1,w3,w6,...} verwerfen. Das wird für jede mögliche Turingmaschine gemacht, zumindest in Gedanken, denn praktisch dürfte so eine Matrix relativ schnell alle Speicher füllen.

So weit so gut, aber was soll all der Blödsinn? Stellen wir uns vor, wir hätten eine Sprache, die immer falsch rechnet. Diese wäre mal ganz sicher nicht rekursiv, wir bräuchten uns nicht einmal Gedanken machen, wann sie unendlich läuft oder nicht definiert ist. So eine Sprache ist die so genannte Diagonalsprache:

Informell gesagt ist das die Sprache, die alle Wörter enthält, die die zugehörige Turingmaschine nicht akzeptiert. Die zugehörige Turingmaschine ist natürlich die, die in der korrespondierenden Zeile steht. Und damit ist D die Sprache, die alle Nullen auf der Diagonale dieser Matrix enthält.

Das führt zu einem ziemlich üblen Widerspruch. Die Annahme ist, dass die Sprache rekursiv ist. Das heißt, dass es eine TM gibt, die auf allen Eingaben hält und genau D akzeptiert. Nennen wir diese TM einfach . Jetzt gibt es zwei interessante Fälle:

1)

Das bedeutet, dass das zu gehörige Wort  zur Sprache gehört. Dann steht an der Stelle in der Matrix nach Definition eine Null. Das würde aber heißen, dass nicht akzeptieren darf, das sagt die Null ja gerade aus. Dann würde die TM aber nicht auf jeder Eingabe korrekt arbeiten, mindestens auf seiner "eigenen" versagt sie.

2)

darf nicht akzeptiert werden, denn es gehört nicht zur Sprache. In der Matrix steht schließlich eine 1. Nun, aber die Sprache enthält ja genau alle Wörter, die von der zugehörigen TM nicht akzeptiert werden, das Wort müsste also zur Sprache gehören, tut es aber nicht.

Wie man sieht führen beide Fälle zum Widerspruch, keine Turingmaschine kann damit D akzeptieren und rechnet dabei immer richtig. Die Sprache ist damit definitiv nicht rekursiv. Das kann man benutzen um die nichtrekursivität des Halteproblems zu beweisen, das wird aber erst im nächsten Beitrag passieren.

Es fällt auf, dass Turingmaschinen, die ein Entscheidungsproblem berechnen am Ende immer entweder eine Null oder eine Eins auf dem Band stehen haben. Man könnte sagen, die Turingmaschine "entscheidet eine Sprache" in dem Sinne, dass sie für jedes Wort, das man auf das Band schreibt, entweder true (Wort gehört zur Sprache) oder false (Gehört nicht zur Sprache) ausgibt. Ein einfaches Beispiel hilft vielleicht.

,,

Das sind alle Zustandsübergänge für . Der erste ist für den Fall, dass ein "a" eingelesen wird. Da passiert nichts weiter, der Kopf bewegt sich nur nach rechts. Wenn ein b gelesen wird, wechselt die TM im den Zustand und schreibt das b zurück aufs Band. Was in passiert, habe ich nicht explizit angegeben, weil es mühselig und langweilig wäre. Was passieren *soll* ist, dass die Turingmaschine das Wort verwirft. Das würde bedeuten, in liefe der Kopf bis ans Ende des Wortes (also bis ein B gelesen wird), läuft dann zurück und löscht dabei jeden Buchstaben. Wenn wieder ein B gelesen wird bedeutet das, dass wir eine Zelle links vom Anfang des Wortes angekommen sind. Wir gehen also noch einen Schritt nach rechts und schreiben eine 0 für false. Ich hoffe mir ist niemand böse, dass ich DAS nicht alles in einer TM codieren wollte. Es sollte aber klar sein, dass es prinzipiell machbar wäre.

Bleibt der letzte Zustandsübergang, nämlich wenn ein B im Zustand gelesen wird. Das würde ja bedeuten, dass wir am Ende des Wortes angekommen sind, ohne jemals auf ein b getroffen zu sein, denn sonst wären wir in gelandet und die TM hätte 0 ausgegeben. Im neuen Zustand würde im Wesentlichen das gleiche passieren wie in , nur dass am Ende eine 1 geschrieben wird.

Die Turingmaschine verwirft also alle Worte, die ein "b" enthalten und akzeptiert alle, die nur aus "a" bestehen. (Bonusfrage: Was ist mit dem leeren Wort? Antwort: Wird auch akzeptiert.) Als Sprache ausgedrückt hieße das übrigens L={ a* }, wobei * den kleenschen Abschluss darstellt, was im Grunde nur "beliebige Anzahl" bedeutet. Und das ist in der Tat eine starke Verbindung zwischen zwei unterschiedlichen Feldern. Eine TM im Entscheidungsmodus und eine Sprache sind ein und dasselbe. Man kann eine Sprache definieren und eine Turingmaschine bauen, die für jedes Wort der Eingabe "1" ausgibt. Umgekehrt gilt das natürlich auch, denn wenn uns jemand eine Turingmaschine gibt, können wir gucken was die für Wörter akzeptiert und uns eine entsprechende Sprache überlegen. Es sind zwei Seiten einer Medaille: Sprachen sind mehr der konstruktive Teil, man will *aktiv* eine Menge von Wörtern generieren und überlegt sich, wie das geht. Die Turingmaschine generiert nichts, sie entscheidet lediglich, ob ein Wort zur Sprache gehört oder nicht.

Wir nähern uns unaufhaltsam dem eigentlichen Thema, denn jetzt kann man sich natürlich überlegen, ob es wirklich für jede Sprache eine entsprechend richtig entscheidende Turingmaschine gibt. Dafür definiere ich das ganze nochmal etwas mathematischer.

Zu einer beliebigen Sprache L gibt es eine so genannte charakteristische Funktion . Das ist jetzt sozusagen das mathematische Äquivalent zu dem oben beschriebenen Sachverhalt. Die Funktion evaluiert zu 1, wenn das Wort in der Sprache ist, sonst zu 0.

Eine Funktion f heißt Turing-berechenbar, falls sie überall definiert ist und falls f von einer TM berechnet werden kann. Dabei muss die TM bei allen Eingaben halten und am Ende wie gefordert 0 oder 1 auf dem Band stehen haben. Eine Sprache L wird Turing-berechenbar genannt, falls die zugehörige Funktion Turing-berechenbar ist. Hier hätten wir also eine formale Verbindung zwischen den drei Betrachtungsweisen. Eine Sprache wird in eine mathematische Funktion umgebastelt, die wiederum von einer Turingmaschine entschieden wird. Übrigens heißt "Turing-berechenbar" auch "rekursiv" und hat nichts mit einem rekursiven Programmaufruf zu tun.

 Rekursiv ist eine Funktion übrigens auch, wenn die entscheidende Turingmaschine nur dann rechnet, wenn die Eingabe aus dem Definitionsbereich ist. Zum Beispiel macht ein Sortieralgorithmus für Ganzzahlen nur für ganzzahlige Eingaben Sinn. Wenn man da einfach ein paar Strings eingeben würde, dürfte die TM formell unendlich weiter rechnen (weil Turingmaschinen keine Exceptions kennen). Trotzdem wäre dieses Verhalten rekursiv. Dann gibt es noch eine letzte wichtige Klasse von Sprachen, die man "rekursiv aufzählbar" nennt. Ich verzichte mal auf eine formale Definition, denn der Unterschied ist auch so leicht zu verstehen. Die TM akzeptiert jedes Wort der Sprache nach wie vor in endlicher Zeit, wenn das Eingabewort aber nicht zur Sprache gehört, rechnet die TM unendlich.

Man, das war lang und langweilig. Damit sind die Vorbereitungen aber endlich abgeschlossen und wir können bald endlich über das Halteproblem sprechen. Bleibt nur noch ein Wort über die Church-Turing-These zu verlieren.

Diese geht nämlich so: "Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen." Was eine Turing-berechenbare Funktion ist, wissen wir ja jetzt. "Intuitiv berechenbare Funktionen" können dagegen nicht so schön definiert werden, man versteht darunter mehr oder weniger alle Funktionen die wir Menschen uns so ausdenken können. Alles was wir Menschen im Prinzip ausrechnen könnten. Sind das nicht *alle* Funktionen, die es gibt? Vermutlich ja, zumindest ist es schwer sich vorzustellen, was es für Funktionen geben könnte, die wir uns nicht ausdenken können. Das liegt aber irgendwie in der Natur der Sache, denn wie sollten wir uns diese Funktionen wohl ausdenken können, wenn es gerade deren Eigenschaft ist, nicht von uns erdacht werden können?

Die These besagt also, dass Computer keine Lücken in ihrer Rechenkraft haben. Alle Dinge die wir entscheiden können, können auch Computer entscheiden. Aber sind alle Computer gleich mächtig? Das sagt uns zumindest die (ebenfalls nicht beweisbare) erweiterte Chruchsche These: "Für je zwei Rechnermodelle R₁ und R₂ gibt es ein Polynom p, so dass t Rechenschritte auf Modell R₁ bei Eingabe der Länge n durch p(t,n) Rechenschritte auf Modell R₂ simuliert werden können." Die Umrechnung von einem auf den anderen Computer soll also maximal in Polynomialzeit machbar sein, was uns Theoretikern zur Zufriedenheit reicht.

Ich glaubs ja kaum. Stephen Wolfram hat 2004 eine Turingmaschine entworfen und 25000$ für einen Beweis ausgelobt, der die Universalität entscheidet. Heute, am gleichen Tag an dem ich zufällig meinen Beitrag über Universelle Turingmaschinen geschrieben habe kommt das rein: Wolfram's 2,3 Turing Machine Is Universal! (Beweis) Damit ist es die kleinste bekannte universelle Turingmaschine. Hier gibts technische Details.