Für interessierte Biber < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sei $k(n)$ die maximale Anzahl der Einsen, die eine Turingmaschine mit $n$-Zuständen auf ein Band schreiben kann und danach terminiert. Ist $k(n)$ rekursiv (aufzählbar), berechenbar?
Hier eine lustige Zusatzaufgabe, die mir durch Zufall wieder in den Sinn gekommen ist: Generiere eine Turingmaschine mit 5 Zuständen, die möglichst viele Einsen auf das Band schreibt und dann terminiert. |
Dieses Problem ist alt, aber lustig. Wir haben das in der Schule mal an einem Turing-Maschinen Simulator ausprobieren können. Also wer Spaß an sowas hat... 
Ich möchte kurz noch die Konstruktion der Turing-Maschine, die ich meine wiederholen:
- Sei [mm] $\Sigma=\{1,2,\#\}$ [/mm] das Bandalphabet.
- Das Band ist unendlich lang und zu keiner Seite beschränkt (es gibt also keinen Anfang, wie es auch manchmal verwendet wird).
- Die Turing-Maschine hat die Zustandsmenge [mm] $Q=\{1,...,n,S\}$, [/mm] wobei $1$ der Startzustand ist und $S$ der Endzustand.
- Die Markierungen für die Bewegung des Lese- und Schreibkopfes auf dem Band sind [mm] $B=\{-1,0,1\}$.
[/mm]
- Die Übergangsfunktion [mm] $\delta$ [/mm] sei deterministisch, d.h.
[mm] $\delta:Q\setminus\{S\}\times\Sigma\to Q\times\Sigma\times [/mm] B$.
Ein kleines Beispiel wäre:
[mm] $\delta(1,\#)\mapsto(2,1,1)$
[/mm]
[mm] $\delta(2,\#)\mapsto(3,1,1)$
[/mm]
[mm] $\delta(3,\#)\mapsto(4,1,1)$
[/mm]
[mm] $\delta(4,\#)\mapsto(5,1,1)$
[/mm]
[mm] $\delta(5,\#)\mapsto(S,1,0)$
[/mm]
und würde folgendes produzieren:
#...#|1|111||1||#...#
wobei die 1 zwischen den einzelnen "|" die Startposition des Lese- und Schreibkopfes ist und die 1 zwischen den beiden "||" die Endposition.
--
Matthias
|
|
|
