Programme von Hand ausführen
Programme von Hand ausführen
In Kursarbeit und Abitur führst du Turingmaschinen auf dem Papier aus: Gegeben sind ein Programm und ein Band, und du notierst Schritt für Schritt, was die Maschine tut. Jeder Schritt läuft dabei so ab wie in Kapitel 2: Zeichen lesen, Regel suchen, schreiben, Zustand wechseln, Kopf bewegen.
Merke: Ablauftabelle
Eine Ablauftabelle hält nach jedem Schritt fest, in welcher Situation die Maschine ist – ihre Konfiguration:
- die Nummer der Regel, die gerade benutzt wurde,
- den Zustand, in dem die Maschine jetzt ist,
- den Bandinhalt und
- die Position des Kopfes (▲).
Schritt 0 ist die Startkonfiguration. Die Tabelle endet mit der Zeile, nach der die Maschine hält.
Beispiel: Maschine A aus dem Einstieg mit dem Band 10, die ersten drei Schritte.
| Nr. | Zustand | Zeichen | neues Zeichen | neuer Zustand | Bewegung |
|---|---|---|---|---|---|
| 1 | 0 | # | # | 1 | R |
| 2 | 0 | 0 | 1 | 0 | L |
| 3 | 0 | 1 | 0 | 0 | L |
| 4 | 1 | # | # | h | L |
| 5 | 1 | 0 | 0 | 1 | R |
| 6 | 1 | 1 | 1 | 1 | R |
| Schritt | Regel | Zustand | Band (Kopf farbig) |
|---|---|---|---|
| 0 | – | 0 | ##10# |
| 1 | 2 | 0 | ##11# |
| 2 | 3 | 0 | ##01# |
| 3 | 1 | 1 | ##01# |
Ablauf von Hand
Aufgabe 1: Führe das Programm Schritt für Schritt aus, bis die Maschine hält.
Ablauf von Hand
Aufgabe 2: Diesmal ist das Programm als Zustandsdiagramm gegeben. Führe es aus, bis die Maschine hält.
Maschine aus Aufgabe 2
Die Maschine aus Aufgabe 2 zum Ausprobieren.
Freitext
Welche Aufgabe erfüllt die Maschine aus Aufgabe 2? Probiere sie dazu mit mehreren Bändern aus.
💡 Zum Speichern deiner Antwort bitte einloggen.
Ablauf von Hand
Aufgabe 3: Im Abitur kann ein Programm auch so notiert sein: Die Zeile nennt den Zustand, die Spalte das gelesene Zeichen, der Eintrag (neues Zeichen ; Bewegung ; neuer Zustand). Führe das Programm aus, bis die Maschine hält.