[ Inhalt ] [ Index ]

Next: Church-Turing-These Up: Turing-Maschinen Previous: Spezielle Turing-Maschinen

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 tex2html_wrap_inline3524 heißt Turing-berechenbar, wenn eine Turing-Maschine existiert, die angesetzt auf die Bandinschrift tex2html_wrap_inline3526 nach endlich vielen Schritten auf dem ersten Zeichen von tex2html_wrap_inline3524 stehenbleibt.

Die tex2html_wrap_inline3530 und tex2html_wrap_inline3524 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:

| *
tex2html_wrap_inline2183 -- tex2html_wrap_inline3546
tex2html_wrap_inline2185 -- tex2html_wrap_inline2243



| *
tex2html_wrap_inline2183 -- tex2html_wrap_inline3558

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:

tex2html_wrap3754

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 tex2html_wrap_inline3560 und eine Turing-Maschine mit n Zuständen tex2html_wrap_inline3564 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 tex2html_wrap_inline3604 mögliche Turingtafeln.

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

tex2html_wrap_inline3606 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:

n tex2html_wrap_inline3606
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 tex2html_wrap_inline3606 noch S(n) berechenbar sind.

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

tex2html_wrap_inline3672

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

tex2html_wrap_inline3682

Dann ist auch F berechenbar durch eine Turing-Maschine tex2html_wrap_inline3686 . tex2html_wrap_inline3686 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 tex2html_wrap_inline3686 , 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:

tex2html_wrap_inline3714 .

Aber tex2html_wrap_inline3716

Außerdem: tex2html_wrap_inline3718

Also tex2html_wrap_inline3720

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

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

Aber tex2html_wrap_inline3728

tex2html_wrap_inline3730

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

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

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 tex2html_wrap_inline3746

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

tex2html_wrap_inline3750

wählen. erhalten wir

tex2html_wrap_inline3752

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




Next: Church-Turing-These Up: Turing-Maschinen Previous: Spezielle Turing-Maschinen

Prof. Dr. Reinhard Völler