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.

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.

T0, T1, T2, ...