[ Inhalt ] [ Index ]

Turing-Berechenbarkeit

Den Begriff berechenbar   haben wir bereits kennengelernt. Eine Funktion f war berechenbar, wenn ein Algorithmus existierte, der für jedes Argument x von f f(x) berechnen konnte.

Jede Turing-Maschine implementiert einen Algorithmus. In Kürze werden wir uns überlegen, daß auch umgekehrt jeder Algorithmus durch eine Turing-Maschine beschrieben werden kann. Wir formulieren die Berechenbarkeit nun für Turing-Maschinen.

Definition: (Turing-Berechenbarkeit  )
Eine Funktion heißt Turing-berechenbar, wenn eine Turing-Maschine existiert, die angesetzt auf die Bandinschrift nach endlich vielen Schritten auf dem ersten Zeichen von stehenbleibt.

Die und sind dabei in unärer Darstellung.

Aufgabe:
Zeigen Sie, daß die Nachfolgerfunktion SUCC(x) und die Addition ADD(x,y) Turing-berechenbar sind!

Wir wissen bereits, daß es viele Funktionen gibt, die nicht berechenbar sind. Im nächsten Abschnitt werden wir eine weitere Funktion kennenlernen, die nicht berechenbar ist.

Wir verwenden die Begriff berechenbar und Turing-berechenbar synonym.

Fleißige Biber

Es ist simpel Turing-Maschinen anzugeben, die eine unendliche Zahl von Strichen auf ein anfangs leeres Band schreiben:

| * -- --

| * --

Man kann auch nicht-periodische Inschriften fabrizieren. Dazu schalten wir die Maschine, die einen einzigen Strich auf das leere Band schreibt und die Kopiermaschine in einer Endlosschleife hintereinander:

Interessanter sind Turing-Maschinen, die irgendwann einmal anhalten. 1982 dachte sich der ungarische Mathematiker Tibor Rado  
das busy beaver Problem   aus:

Man nehme ein beidseitig unendliches Band, das Bandalphabet und eine Turing-Maschine mit n Zuständen und einem zusätzlichen Haltezustand H.

In jedem Schritt muß die Turing-Maschine ein Symbol schreiben und eine Bewegung nach links oder rechts machen oder aber anhalten. Die Maschine mit n Zuständen, die angesetzt auf das leere Band die meisten Striche schreibt, erhält den Titel fleißiger Biber  . Die Strichfolge darf Lücken enthalten.

Beispiel:
Ein busy beaver mit 3 Zuständen

| *

1 (3, |, L) (2, |, R)

2 (2, |, R) (1, |, L)

3 (H, |, R) (2, |, L)

H -- --

Nach 13 Schritten hat die Maschine 6 Striche auf das Band geschrieben und hält an.

Wir überlegen uns zunächst, daß für jedes n ein solcher fleißiger Biber existieren muß:

Die Zahl der Turingmaschinen mit n Zuständen und einem Bandalphabet mit zwei Elementen ist endlich. Also liste man alle Turing-Maschinen auf, und suche die Maschine heraus, die die meisten Striche produziert.

Wir können die Zahl der möglichen Turing-Maschinen sogar exakt angeben:

n Zustände und ein zweielementiges Alphabet ergeben eine Turingtafel mit 2n Einträgen für die Nichtendzustände.

Jeder Eintrag besteht aus einem Tripel (Folgezustand, Symbol, Bewegung).

Davon gibt es (n+1) * 2 * 2. Macht zusammen mögliche Turingtafeln.

bezeichne nun die maximale Anzahl von Strichen einer Turing-Maschine mit n Zuständen, S(n) die maximale Anzahl der Schritte.

ist eine wohldefinierte Funktion; für kleine Werte von n kann man die Funktionswerte auch ganz gut angeben.

Klein heißt hier, für Werte von 1 bis 4. Für größere Werte hat man nur einige untere Grenzen.

In [2] finden wir die folgende Tabelle:

1 1

2 4

3 6

4 13

5 >= 4098

1984 wurde im Scientific American von einem 5-Zustands-Biber berichtet, der von dem deutschen Informatiker Uwe Schult gefunden wurde und 501 Striche produzierte. Der wurde später von einem anderen amerikanischen Biber abgelöst, der 1915 Striche produzierte. 1989 wurde dann in Deutschland wieder ein Biber gesichtet, der nach einer dreitägigen Jagd mit einem Hochgeschwindigkeitscomputer 4098 Striche lieferte.

Die folgende Turing-Maschine ist ein Kandidat für den Titel busy beaver mit 6 Zuständen:

| *

1 (1, |, R) (2, |, R)

2 (2, |, L) (3, |, L)

3 (4, |, L) (6, *, R)

4 (5, *, L) (1, |, R)

5 (6, |, L) (H, |, L)

6 (3, *, L) (1, *, L)

H -- --

Sie sollten einmal überprüfen, daß dieser Biber 95.524.079 Striche produziert und nach 8.690.333.381.690.951 Schritten anhält. Das ist zwar eine ganze Menge, aber immer noch endlich...

Wir zeigen jetzt, daß weder noch S(n) berechenbar sind.

Die Idee ist, daß wir nachweisen, daß größer als jede beliebige berechenbare Funktion ist, d.h. daß für jede berechenbare Funktion f gilt:

Eine Turing-Maschine, die f(n) berechnet, wird auf das Band angesetzt, auf dem n Striche stehen und hält nach endlich vielen Schritten mit der Bandinschrift von f(n) Strichen.

Sei nun f eine beliebige berechenbare Funktion. Wir definieren

Dann ist auch F berechenbar durch eine Turing-Maschine . habe n Zustände.

Wir betrachten eine Turing-Maschine M, die x Striche auf das zunächst leere Band schreibt und dann auf dem letzten Strich stehenbleibt. Das schafft sie mit x Zuständen.

Dahinter schalten wir , die dann F(x) Striche auf das Band schreibt. Das kostet noch einmal n Zustände. Wir setzten M(F) ein weiteres Mal auf das Band an, auf dem nun x+F(x) Striche stehen. So erhalten wir ein Band mit insgesamt x + F(x) + F(F(x)) Strichen. Diese Striche wurden von einer Maschine mit x + n + n Zuständen geschrieben.

Eine fleißiger Biber mit x + 2n Zuständen wird mindestens soviele Striche schreiben wie unsere Maschine. Also gilt:

.

Aber

Außerdem:

Also

F(x) ist aber monoton, d.h.

folglich: F(F(x)) > F(x + 2n).

Aber

f war beliebig, berechenbar: folglich kann nicht berechenbar sein.

Daß S(n) nicht berechenbar ist, ist klar, da eine Turing-Maschine, die Striche auf das Band schreibt, mindestens Bewegungen machen muß. Also .

Der Beweis, den wir eben geführt haben, wurde bereits 1962 von Rado   gefunden. 1964 entdeckte M.W. Green  , daß die folgende Beziehung gilt:

f berechenbar

Wenn wir für f z.B. die Funktion

wählen. erhalten wir

Nun kann man auch verstehen, daß es wenig aussichtsreich erscheint, nach fleißigen Bibern mit 6 und mehr Zuständen zu suchen.