 |
|||
| HSG |
|
Die Rado-Funktion Σ
Zitat aus Ulrich Mayr, Theoretische Informatik am PC:
Die von T.Rado 1962 angegebene Funktion Σ bezieht sich auf das Problem, eine Turing-Maschine über {' ','I'} mit genau n Zuständen zu suchen, die nach dem Start auf dem leeren Band möglichst viele Striche schreibt und dann stehen bleibt. Dabei sollen die Bewegungen L, R, S erlaubt sein, nicht aber N (keine Bewegung). Eine solche Maschine wird scherzhaft als fleißiger Biber bezeichnet. (Biber sammeln bekanntlich Holzstäbe um Bäche zu stauen.)
Σ(n) := Die maximale Anzahl von Strichen, die eine Turing-Maschine
über {' ','I'} mit genau n Zuständen produzieren kann, die nach
einem Start auf dem leeren Band zum Stehen kommt.
Bemerkung zu JFlap
JFlap kennt keine Kopfbewegung 'Stopp' und stoppt nur in einem finalen Zustand. Man kann sich nun so behelfen, dass statt 'Stopp' 'Stay' eingegeben wird und ein zusätzlicher finaler Zustand zum Stoppen verwendet wird.
Σ(1)
Alle entsprechenden Maschinen kann man durch die zugeordnete Turingtabelle angeben.
Zustand gelesen : neuer Zustand geschrieben Kopfbewegung ---------------------------------------------------------- z0 ' ' : z0 ▒ ▒ z0 'I' : z0 ▒ ▒
Das geschriebene Zeichen kann ' ' oder 'I' sein, die Kopfbewegung L, R oder S. Es gibt also (2*3)**(2*1) = 36 Möglichkeiten, die Tabelle aufzustellen.
Reduzierung der Anzahl der zu untersuchenden Maschinen
Herr Mayr führt in seinem Buch dazu Folgendes aus:
Etliche Maschinen scheiden als Kandidaten für den fleißigen Biber von vornherein aus,
wenn z.B. erkennbar ist, dass sie nicht halten oder dass die Anzahl der geschriebenen Striche
zu gering ist.
Im Folgenden sollen einige einfache Überlegungen in diese Richtung angestellt werden.
Dazu betrachten wir zuerst die Stoppzeilen der zu untersuchenden Maschinen.
Anzahl der Stoppbefehle:
Wir brauchen nur Maschinen zu untersuchen, die genau einen Stoppbefehl besitzen. Existieren mehrere
Stoppbefehle bei einer Maschine, so wird genau einer davon ausgeführt, wenn es zum Stopp kommt.
Die anderen Stoppbefehle sind für den Ablauf überflüssig und können deshalb abgeändert werden,
ohne dass die Maschine ihr Verhalten beim Start auf dem leeren Band ändert. Wir ändern bei diesen
Befehlen die Bewegung S in R um.
Form des Stoppbefehls:
Der Folgezustand ist ohne Bedeutung. Wir nehmen z0 an. Als Folgezeichen können wir 'I' annehmen,
anderenfalls ist die Maschine nicht optimal.
Lage des Stoppbefehls in der Tafel:
Wir setzen fest, dass der Stoppbefehl, falls er nicht beim Anfangszustand z0 auftritt, bei einem
der beiden Befehle im Zustand zn-1 zu finden sein muss. Steht der Stoppbefehl bei einem anderen Zustand,
so kann durch Umnummerieren der Zustände erreicht werden, dass er zum letzten Zustand zn-1 gehört.
Bei einem Stoppbefehl der Form ( z0 ' ' : z0 'I' S ) wird genau ein Strich geschrieben.
Die Maschine kann für n>1 nicht optimal sein. Es verbleiben drei mögliche Stoppbefehle, von denen jeweils einer
in jeder zu untersuchenden Maschine auftreten muss.
z0 'I' : z0 'I' S zn-1 ' ' : z0 'I' S zn-1 'I' : z0 'I' S
Wir betrachten nun die Startzeile der Maschinen.
Startbefehle mit S als Bewegung sind bereits von der weiteren Betrachtung ausgeschlossen worden. Wir
legen R als Bewegung beim Startbefehl fest. Maschinen mit L an dieser Stelle haben ein Pendant,
das sich genau spiegelbildlich bewegt, wenn wir sämtliche Bewegungen L mit R und umgekehrt austauschen.
Die Anzahl der produzierten Striche bleibt dabei unverändert. Tritt z0 als Folgezustand auf,
so wandert die Maschine nach rechts, ohne jemals zu halten. Es verbleiben z1 bis zn-1 als Folgezustände.
Ein Folgezustand z2,...,zn-2 kann durch Indextausch mit z1 den Platz wechseln.
Mögliche Folgezustände des Startbefehls sind also z1 und zn-1.
Ist das Folgezeichen ein ' ', dann betrachtet man den ersten Befehl der Form
( zi ' ' : Folgezustand 'I' Bewegung ), der beim Start auf dem leeren Band ausgeführt wird,
und vertauscht zi mit z0. Die neue Maschine lässt Anfangsbewegungen weg, bei denen kein 'I'
geschrieben wird. Danach ist ihr Verhalten dem der Ausgangsmaschine gleich. Als Folgezeichen kommt also nur 'I'
in Frage.
Mögliche Startzeilen:
z0 ' ' : z1 'I' R z0 ' ' : zn-1 'I' R
Σ(1)
Die Überlegungen zur Reduzierung der Maschinen gelten nur für n>1. Manche Argumente lassen sich aber auch auf n=1 anwenden. Wäre die Startzeile (z0 ' ' : z0 ▒ R), so würde die Maschine unendlich nach rechts laufen, da sie immer auf ein leeres Feld trifft und im Zustand bleibt. Analog geht es für die Kopfbewegung L schief. Also muss die Kopfbewegung S sein. Das gedruckte Zeichen muss ein Strich sein, sonst ist die Maschine nicht optimal. Der zweite Übergang wird nicht benutzt, kann also beliebig gewählt werden. Es gibt also sechs 'fleißige Biber' für n=1.
z0 ' ' : z0 'I' S z0 'I' : z0 ▒ ▒
Diese Maschinen schreiben genau einen Strich und bleiben dann stehen, also Σ(1) = 1.
Σ(2)
Die Darstellung lehnt sich eng an das Buch von Herrn Mayr an.
Als mögliche Startzeile bleibt nur
z0 ' ' : z1 'I' R
Von den drei möglichen Stoppzeilen führt
z1 ' ' : z0 'I' S
zu der Maschine
die genau zwei Striche schreibt und dann stehen bleibt. Die nicht angegebenen Transitionen werden dabei nicht gebraucht.
Die verbleibenden Stoppzeilen führen zu Maschinen der Gestalt
Typ A Typ B
z0 ' ' : z1 'I' R z0 ' ' : z1 'I' R
z0 'I' : z0 'I' S z0 'I' : ▒ ▒ ▒
z1 ' ' : z0 ▒ L z1 ' ' : z0 ▒ L
z1 'I' : z0 ▒ ▒ z1 'I' : z0 'I' S
Für die schraffierten Leerstellen sollen nun alle Möglichkeiten durchgegangen werden.
Typ A
1) ' ' 2) 'I' 3) ' ' 4) 'I' 5) ' ' 6) 'I' 7) ' ' 8) 'I'
' ' L ' ' L 'I' L 'I' L ' ' R ' ' R 'I' R 'I' R
Typ B
9) z0 ' ' L 10) z0 'I' L 11) z0 ' ' R 12) z0 'I' R 13) z1 ' ' L 14) z1 'I' L 15) z1 ' ' R 16) z1 'I' R
' ' ' ' ' ' ' ' ' ' ' ' ' ' ' '
17) z0 ' ' L 18) z0 'I' L 19) z0 ' ' R 20) z0 'I' R 21) z1 ' ' L 22) z1 'I' L 23) z1 ' ' R 24) z1 'I' R
'I' 'I' 'I' 'I' 'I' 'I' 'I' 'I'
Diese 24 Maschinen b2_1 bis b2_24 müssen nun einzeln untersucht werden. Beginnen wir mit b2_1.
z0 ' ' : z1 'I' R z0 'I' : z0 'I' S z1 ' ' : z0 ' ' L z1 'I' : z0 ' ' L
Benutzt man JFlap, so ist in der weiter vorne beschriebenen Art ein finaler Stoppzustand hinzuzufügen.
Die Maschine hält nicht, der Strich wandert immer weiter nach links. Wie wäre hier ein exakter Beweis zu führen?
b2_2
Die Maschine produziert bliebig viele Striche und läuft nach links weg, hält also nicht.
b2_3
Die Maschine stoppt mit zwei Strichen.
b2_4
Die Maschine stoppt mit drei Strichen. Sie ist also bisher der Favorit für den Titel 'Fleißiger Biber'.
Aufgaben
In der beschriebenen Weise sind die weiteren 20 Maschinen zu untersuchen.
b2_0 : 2 (vorher schon ausgesondert) b2_1 : hält nicht b2_2 : hält nicht b2_3 : 2 b2_4 : 3 b2_5 : 1 b2_6 : 2 b2_7 : 1 b2_8 : 2 b2_9 : hält nicht b2_10 : 2 b2_11 : hält nicht b2_12 : hält nicht b2_13 : hält nicht b2_14 : hält nicht b2_15 : hält nicht b2_16 : hält nicht b2_17 : hält nicht b2_18 : 3 b2_19 : hält nicht b2_20 : hält nicht b2_21 : 3 b2_22 : 4 - ein 'fleißiger Biber' b2_23 : 1 b2_24 : 2
Die Rado-Funktion Σ ist nicht berechenbar.
Das beweist Christian Seise, Abitur 2006 in seinem Referat 'Fleißige Biber'.
Beamtenbiber und andere neue Biberarten
In seinem Artikel 'Fleißige Biber' in Spektrum der Wissenschaft, Computerkurzweil II, 1988 erwähnt A.K. Dewdney (S.96,97) interessante neue Biberarten. So lernt man z.B. den Castor ministralis (Trivialname: Beamtenbiber) kennen. Er will möglichst weit vorwärts kommen ohne irgendetwas (dh. I zu schreiben) zu leisten. Der Castor scientificus (Trivialname: Wissenschaftsbiber) bemüht sich sehr (macht viele Schritte), kommt aber nicht soweit wie der Beamtenbiber. Auch er erreicht letztlich nichts. Der Castor exflippus (Trivialname: Aussteigerbiber) hat kein Interesse am Vorwärtskommen und keins an der Arbeit. Er will lediglich möglichst lange leben.
Aufgabe
Erwecke die neuen Biberarten mit Hilfe der Turing-Simulation zum Leben.
Links
- Fleißiger Biber - wikipedia