Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Turing-Beispielprogramme

Es werden hier ein Incrementator, ein Decrementator, ein Paritätsprüfer, ein Programm zur Addition und ein Programm zu Subtraktion für die Turingmaschine vorgestellt.

Incrementator

Dieses Programm erhöht die Anzahl der Einsen auf dem Band um eine Eins.

 0 1 1 R 1            bedeutet: die TM ist im Zustand 0, liest eine 1, schreibt eine 1, geht nach rechts und ist im Zustand 1
 1 1 1 R 1                      die TM ist im Zustand 1, liest eine 1, schreibt eine 1, geht nach rechts und ist im Zustand 1
 1 # 1 S 2                      die TM ist im Zustand 1, liest ein Leereichen, schreibt eine 1, stoppt und ist im Zustand 2

Decrementator

Dieses Programm vermindert die Anzahl der Einsen auf dem Band um eine Eins. (Es wird hier davon ausgegangen, dass mindestens eine Eins auf dem Band steht.)

 0 1 1 R 0
 0 # # L 1
 1 1 # S 1

Paritätsprüfer

Dieses Programm erzeugt eine gerade Anzahl von Einsen auf dem Band. Wenn auf dem Band eine gerade Anzahl von Einsen ist, dann werden die Einträge auf dem Band so gelassen wie sie sind. Ist die Anzahl der Einsen auf dem Band ungerade, dann wird auf dem Band eine Eins hinzugefügt. (siehe Weblink 1 und 2)

Idee: Wir gehen die Einsen auf dem Band der Reihe nach durch und wechseln jedesmal den Zustand. Also erste Eins Zustand 0, zweite Eins Zustand 1, dritte Eins Zustand 0, vierte Eins Zustand 1, fünfte Eins Zustand 0 usw. Das bedeutet, bei den Einsen an der ungeraden Stelle ist die TM im Zustand 0, bei den Einsen an der geraden Stelle ist die TM im Zustand 1.

 0 1 1 R 1
 1 1 1 R 0
 1 # 1 S 2
 0 # # S 2

Programm zur Addition

Bei diesem Programm sind auf dem Band m Einsen, dann ein Leerzeichen und dann n Einsen vorhanden. Durch das Programm sollen die Einsen auf dem Band "zusammengefügt" werden, sodass m+n Einsen hintereinander auf dem Band stehen.

Idee: Wir gehen die Einsen auf dem Band der Reihe nach durch bis zum Leerzeichen und schreiben da eine Eins. Wir gehen dann die zweite Gruppe von Einsen (also die 2. Zahl) durch bis zum Ende, gehen wieder eine Eins zurück und löschen diese Eins.

Programm zu Subtraktion

Bei diesem Programm sind auf dem Band m Einsen, dann ein Leerzeichen und dann n Einsen vorhanden. Dabei ist die Anzahl m der Einsen auf dem Band größer als die Anzahl n. Durch das Programm werden die Einsen auf dem Band abgezogen, sodass m-n Einsen hintereinander auf dem Band stehen.

Das Programm subtraktion.tm kann hier als zip-File runtergeladen werden.

Aufgaben

1. Testen Sie das Programm Incrementator mit dem Turing-Simulator.
2. Erläutern Sie das Programm Decrementator, wie es im Beispiel Incrementator angegeben ist (die Kommentare).
3. Was macht das Programm Decrementator? Testen Sie das Programm mit dem Turing-Simulator.
4. Erläutern Sie das Programm Paritätsprüfer, wie es im Beispiel Incrementator angegeben ist (die Kommentare).
5. Testen Sie das Programm Paritätsprüfer mit dem Turing-Simulator für verschiedene ungerade und gerade Anzahl von Einsen.
6. Erstellen Sie das Programm Addition und testen Sie es mit dem Turing-Simulator.
7. Laden Sie das Programm für die Subtraktion herunter, laden Sie dieses in den Turing-Simulator und testen Sie das Programm.
8. Erläutern Sie das Programm Subtraktion, wie es im Beispiel Incrementator angegeben ist.

Weblinks

1. Paritätsprüfung (Uni Oödenburg)
2. Paritätsprüfung (IT-Wissen.info)

zurück