[ Inhalt ] [ Index ]

Simulation von Turing-Maschinen

In den vorangegangenen Abschnitten haben wir immer neue Turing-Maschinen für verschiedene Probleme erstellt. Wir werden nun eine Turing-Maschine betrachten, die sich ähnlich wie ein Computer programmieren läßt und dann beliebige Turing-Maschinen simulieren   kann. Eine solche Maschine wird auch als UTM   , als Universelle Turing-Maschine   bezeichnet.

Turing-Maschinen sind sozusagen die Spitzenmodelle der Automaten, die wir zur Spracherkennung einsetzen können, da ja jeder nur denkbare Algorithmus durch eine Turing-Maschine ausgeführt werden kann. Dennoch gibt es Sprachen, die nicht von einer Turing-Maschine erkannt werden können, wie an sich leicht überlegt (wie eigentlich?).

Eine dieser Sprachen werden wir gleich kennenlernen.

Außerdem wollen wir eines der wichtigsten Probleme der Informatik, das sogenannte Halteproblem   kennenlernen. Dieses Problem hat mit der Nichtentscheidbarkeit   einer bestimmten Menge zu tun. (Wann war eine Menge eigentlich noch entscheidbar??)

Besorgen wir uns also zunächst einmal das notwendige Handwerkszeug.

Die Universelle Turing-Maschine

Die UTM soll so funktionieren, daß sie mit einer Bandinschrift, die die Codierung einer Turing-Maschine und die Eingabe für diese Turing-Maschine enthält, gestartet wird. Nun verhält sich die UTM so, wie die codierte Turing-Maschine, d.h. entweder hält sie nie an, weil die simulierte Maschine auch nicht stoppt, oder aber sie stoppt irgendwann mit der gleichen Bandinschrift.

Für die Codierung der Turing-Maschine gibt es verschiedene Möglichkeiten.

Wir betrachten eine abzählbar unendliche Menge S von Zuständen, von denen jede konkrete Turing-Maschine T eine endliche Teilmenge verwendet.

ist eine abzählbar unendliche Menge von potentiellen Endzuständen. ist immer der Startzustand.

Das Bandalphabet B bestehe immer aus .

Die Codierung der Überführungsfunktion einer Turing-Maschine T sieht nun so aus:

Jeder Übergang wird codiert als

Die Codierungen aller möglichen Übergänge stehen hintereinander auf dem Band.

Die aktuelle Konfiguration von T muß ebenfalls codiert werden. Eine solche Konfiguration besteht aus einem Tupel (v,b,w,s) wobei v die Bandinschrift links vom S/L-Kopf, b das aktuelle Symbol, w die Inschrift rechts vom Kopf und s den Zustand bezeichnet. Alle diese Informationen können wie oben zeichenweise codiert werden.

Die Codierung der Überführungsfunktion legt sie zu simulierende Turing-Maschine eindeutig fest. Die verwendete Folge aus 0 und 1 kann man nun als (zugegeben möglicherweise sehr große Binärzahl) betrachten, die die Turing-Maschine eindeutig charakterisiert.

Definition: (Simulation einer Turing-Maschine [9])
Es bezeichne bzw. die oben beschriebene Codierung der Überführungsfunktion und der Konfiguration von Turing-Maschinen.

Eine universelle Turing-Maschine UTM simuliert eine Turing-Maschine T, wenn gilt:

U befindet sich zu Anfang in der Initialkonfiguration

, Initialkonfiguration von T

falls T die Konfigurationen durchläuft,

durchläuft UTM die Konfigurationen

...

...

UTM hält (in einer Finalkonfiguration) genau dann,
wenn T (in einer Finalkonfiguration) hält.

Es gibt noch andere Verfahren Turing-Maschinen zu codieren, insbesondere kann man die Codierung wesentlich kompakter gestalten. Eine ausführliche Beschreibung einer effizienteren Codierung findet man z.B. in [7].

Eine Sprache, die von keiner Turing-Maschine akzeptiert wird

Da wir jeder Turing-Maschine eine Zahl zuordnen können, kann man von der 1., 2., ..., i-ten Turing-Maschine sprechen.

Satz:
Die Sprache wird von keiner Turing-Maschine akzeptiert.

Beweis:
Angenommen die Turing-Maschine akzeptiert .

Dann gilt .

Nun betrachten wir .

(denn )

(wegen Definition )

Widerspruch!!

Turing-aufzählbare Sprachen

Die Turing-aufzählbaren Sprachen sind genau die Sprachen, die auch von Turing-Maschinen akzeptiert werden. Diese weitere Charakterisierung der Sprachklasse besagt der folgende

Satz:
Sei E ein Alphabet, . Dann gilt:

M ist Turing-aufzählbar .

Wenn bzw. die Menge der aufzählbaren bzw. Turing-aufzählbaren Sprachen bezeichnen, gilt also:

Beweis:
'' '': Sei M Turing-aufzählbar. Dann existiert eine surjektive Funktion , die Turing-berechenbar ist.

Sei die Turing-Maschine, die f berechnet. Wir verwenden die UTM, um mit den Eingaben 0, 1, 2, 3, ... zu simulieren.

Wir denken uns nun eine weitere Turing-Maschine T, die die Zahlen 0, 1, 2, 3, ... produziert und außerdem simuliert.

T funktioniert nun so, daß sie, angesetzt auf ein Wort w, nacheinander die Zahlen 0, 1, 2, ... produziert und durch Simulation von f(0), f(1), f(2), ... berechnet. Ist irgendwann f(i) = w hält T an.

'' '': Sei , d.h. es gibt eine Turing-Maschine, die M akzeptiert. Gesucht ist eine Turing-Maschine , die nacheinander die Funktionswerte produziert, und genau alle Elemente aus M liefert.

Wir konstruieren eine Turing-Maschine T, die alle Zahlenpaare (i,j) generiert, und zwar in der folgenden Reihenfolge:

Ferner soll T die Worte aufzählen.

T generiert nun die Zahlenpaare (i,j) in der besagten Reihenfolge. Für jedes Paar (i,j) wird dann für i Schritte die Turing-Maschine auf losgelassen. Ist , so wird irgendwann ein Paar (i,j) erzeugt, so daß innerhalb von i Schritten akzeptiert wird.

Zu jeder Eingabe werden nun die Zahlenpaare generiert und das (k+1)-te akzeptierte Wort ausgegeben.

Damit haben wir eine Turing-Maschine gefunden, die surjektiv auf M abbildet.

Das Halteproblem

  Schön wär's ja, wenn wir einen Compiler um die Option ''suche Endlosschleifen'' erweitern könnten. Dann könnte der Compiler beim Compilieren eine Warnung ausgeben, daß ein Programm möglicherweise nicht terminiert. Leider geht das nicht, wie der folgende Satz zeigt:

Satz:
Das Halteproblem für Turing-Maschine ist unentscheidbar, d.h. es gibt keine Turing-Maschine, die für jede beliebige Turing-Maschine T und jedes beliebige Eingabewort w entscheiden kann, ob T angesetzt auf w anhält oder nicht.

Beweis:
Wir werden diesen Satz gleich zweimal beweisen (weil's so schön ist!).

1. Angenommen, es gäbe eine solche Turing-Maschine . Wir zeigen, daß es dann auch eine Turing-Maschine gibt, die die Sprache aus dem letzten Abschnitt akzeptiert. Und das kann ja nicht sein.

Wir skizzieren die Arbeitsweise dieser Turing-Maschine:

• Sei . Bestimme mit .
• Bestimme .
• Bestimme mit , ob angesetzt auf hält.
• Wenn nicht anhält, akzeptiere .
• Wenn anhält, akzeptiere , falls nicht akzeptiert. Das kann man mit der UTM simulieren.

Damit ist sogar entscheidbar! Und das kann ja nun wirklich nicht wahr sein!

2. Man kann sich auch von der Nichtexistenz der Turing-Maschine so überzeugen:

Wenn existiert, dann bauen wir die folgende Turing-Maschine

Diese Maschine nennen wir A. wenden wir auf eine Eingabe w und eine Codierung einer Turing-Maschine X an.

Wenn X bei der Eingabe w anhält, so soll auf |, sonst auf * stehenbleiben.

Wenn wir jetzt A auf die Codierung von X loslassen, wird erst einmal X kopiert. Dann prüft , ob X angesetzt auf X hält oder nicht. Wenn X hält, so läuft A in eine Endlosschleife.

Für A existiert auch eine Codierung, die wir nun auf das Band schreiben.

Wenn A nun losläuft, erhalten wir einen Widerspruch, da A anhält, wenn A nicht anhält und umgekehrt.