Eine Aufzählung aller Turingmaschinen
Zielsetzung - Überblick über alle Turingmaschinen
Um Aussagen über die Grenzen der Berechenbarkeit machen zu können, müssen wir ein präzise beschriebenes Berechnungsmodell verwenden. Nach dem Satz über die Äquivalenz von Berechnungsmodellen ist es dabei egal, welches Berechnungsmodell wir verwenden.
Hier soll im Folgenden die Turingmaschine als Berechnungsmodell benutzt werden.
Dabei werden wir ausschließlich einfache Turingmaschinen betrachten.
Wir setzen zudem voraus, dass auf dem Band außer dem speziellen Bandsymbol B
für ein leeres Feld nur das Symbol I
vorkommen soll.
Schließlich setzen wir voraus, dass die betrachteten Turingmaschinen genau einen Endzustand zS
haben.
Ziel ist es, einen Überblick über alle Turingmaschinen mit den eben formulierten Einschränkungen zu gewinnen. Wenn dieser Überblick vorliegt, können wir eventuell Aussagen über die mit diesen Turingmaschinen berechenbaren Funktionen treffen.
Aufzählung von Turingmaschinen mit einem Zustand
Wir betrachten zunächst nur Turingmaschinen mit nur einem Zustand (außer dem Endzustand zS
).
Wie dieser Zustand benannt wird,
spielt dabei keine Rolle. Wir gehen von der Bezeichnung z0
aus.
Dieser Zustand ist dann auch der Startzustand.
Eine Turingmaschine wie diese kann eindeutig durch eine Übergangstabelle der folgenden Gestalt beschrieben werden.
aktueller Zustand | gelesenes Symbol | neuer Zustand | zu schreibendes Symbol | Bewegung |
---|---|---|---|---|
z0 | B | z0 | B | L |
z0 | I | z0 | I | L |
Eine solche Übergangstabelle schreiben wir kurz so auf:
z0 B z0 B L; z0 I z0 I L;
Durch eine Variation der Folgezustände, der zu schreibenenden Symbole und der Bewegungen kann man systematisch alle möglichen Übergangstabellen erzeugen. Die folgende Auflistung zeigt den Anfang einer solchen systematischen Erzeugung. Hier werden (von rechts nach links) zunächst die möglichen Bewegungen, dann die zu schreibenden Symbole, anschließend die Folgezustände der zweiten Übergangstabellenzeile variiert, danach wird das gleiche Verfahren auf die erste Übergangstabellenzeile angewandt.
z0 B z0 B L; z0 I z0 B L; z0 B z0 B L; z0 I z0 B R; z0 B z0 B L; z0 I z0 I L; z0 B z0 B L; z0 I z0 I R; z0 B z0 B L; z0 I zS B L; z0 B z0 B L; z0 I zS B R; z0 B z0 B L; z0 I zS I L; z0 B z0 B L; z0 I zS I R; z0 B z0 B R; z0 I z0 B L; ... z0 B zS I R; z0 I zS I R;
Aufgabe 1
(a) Kannst du die begonnene Aufzählung fortsetzen? Zur Kontrolle: Es gibt 64 verschiedene Möglichkeiten.
(b) Begründe, dass es 64 verschiedene Turingmaschinen (mit den gemachten Einschränkungen) mit genau einem Zustand (außer dem Endzustand) gibt.
Aufzählung von Turingmaschinen mit zwei Zuständen
Wir betrachten jetzt Turingmaschinen mit genau 2 Zuständen (außer dem Endzustand zS
).
Die Zustände sollen mit z0
und z1
bezeichnet werden.
Der Zustand z0
soll auch hier der Startzustand sein.
Eine mögliche Übergangstabelle für eine solche Turingmaschine könnte (in unserer Kurzschreibweise) so aussehen:
z0 B z0 B L; z0 I z0 I R; z1 B z0 B L; z1 I z0 I R;
Auch hier lassen sich systematisch alle möglichen Turingmaschinen mit zwei Zuständen (außer dem Endzustand) systematisch erzeugen und anordnen. Die folgende Auflistung zeigt den Anfang einer solchen systematischen Erzeugung.
z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I L; z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I R; ... z0 B zS I R; z0 I zS I R; z1 B zS I R; z1 I zS I R;
Aufgabe 2
(a) Kannst du die begonnene Aufzählung um einige wenige Turingmaschinen fortsetzen?
(b) Wie viele Turingmaschinen gibt es hier?
Aufzählung aller Turingmaschinen
Das beschriebene Verfahren zur Aufzählung von Turingmaschinen lässt sich weiter fortsetzen. Nach den Turingmaschinen mit 2 Zuständen folgen die mit 3 Zuständen usw..
T0: z0 B z0 B L; z0 I z0 B L; T1: z0 B z0 B L; z0 I z0 B R; ... T64: z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I L; T65: z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I R; ... T20800: z0 B z0 B L; z0 I z0 I L; z1 B z0 B L; z1 I z0 I L; z2 B z0 B L; z2 I z0 I L; ...
Im folgenden Satz fassen wir die gewonnenen Erkenntnisse zusammen.
Satz (über die Aufzählbarkeit von Turingmaschinenvarianten)
Turingmaschinen mit einer fest vorgegebenen Symbolmenge (Eingabesymbole + Bandsymbole) kann man systematisch (algorithmisch) erzeugen.
T0, T1, T2, ...
Jede Turingmaschine kommt in dieser Auflistung vor. Man kann (mit einem geeigneten Algorithmus) zu jeder natürlichen Zahl n die zugehörige Turingmaschine Tn bestimmen. Umgekehrt kann man (mit einem geeigneten Algorithmus) zu jeder Turingmaschine T die Platznummer n in der Auflistung bestimmen.