Ein Zählerstand, der um eins weiterläuft
Eine Turingmaschine ist ein einfaches Modell eines Computers: Ein Kopf liest und schreibt Zeichen auf einem Band und folgt dabei einer Regeltabelle. Mit ihr lässt sich zum Beispiel ein Zählerstand in Binärschrift um eins erhöhen.
Mehr braucht ein Computer im Prinzip nicht. Was ein Rechner überhaupt berechnen kann, lässt sich an dieser kleinen Maschine untersuchen.
Am Ende dieser Lektion
Notiz
Ich kann eine Turingmaschine Schritt für Schritt auf ihrem Band verfolgen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Band | ein unendlicher Streifen aus Feldern, je ein Zeichen | 1011 |
| Kopf | liest und schreibt das Feld, auf dem er steht | |
| Regeltabelle | sagt zu Zustand und Zeichen, was zu tun ist | |
| Haltezustand | ein Zustand, in dem die Maschine anhält | |
| Leeres Feld | ein Feld ohne Zeichen, hier geschrieben als _ | |
| Berechenbar | so, dass eine Turingmaschine es ausrechnen kann |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Turingmaschine hat Band, Kopf und Regeln
Das Band ist unendlich lang und besteht aus Feldern. Auf jedem steht ein Zeichen oder nichts. Der Kopf steht auf genau einem Feld, liest es und darf es überschreiben.
In jedem Schritt schlägt die Maschine in der Regeltabelle nach. Zustand und gelesenes Zeichen ergeben ein neues Zeichen, eine Richtung und einen neuen Zustand. Im Haltezustand hört sie auf.
Die Regeln der Maschine „plus eins“
| Zustand | Liest | Schreibt | Richtung | Neuer Zustand |
|---|---|---|---|---|
| suche | 0 | 0 | rechts | suche |
| suche | 1 | 1 | rechts | suche |
| suche | _ | _ | links | addiere |
| addiere | 1 | 0 | links | addiere |
| addiere | 0 | 1 | links | halt |
| addiere | _ | 1 | links | halt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ablauf auf dem Band 1011
| Schritt | Band | Kopf auf | Zustand danach |
|---|---|---|---|
| Start | 1011 | erstes Feld | suche |
| 1 bis 4 | 1011 | hinter der letzten Ziffer | suche |
| 5 | 1011 | letzte Ziffer | addiere |
| 6 | 1010 | drittes Feld | addiere |
| 7 | 1000 | zweites Feld | addiere |
| 8 | 1100 | erstes Feld | halt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine feste Maschine, die Bits umkehrt
# Eine feste Maschine: sie kehrt jedes Bit um und haelt am Bandende.
band = list("1011_")
kopf = 0
zustand = "lauf"
schritt = 0
while zustand != "halt":
symbol = band[kopf]
if symbol == "1":
band[kopf] = "0"
kopf = kopf + 1
elif symbol == "0":
band[kopf] = "1"
kopf = kopf + 1
else:
zustand = "halt"
schritt = schritt + 1
print(schritt, "".join(band), "Kopf bei", kopf, "Zustand", zustand)
# Aendern Sie das Band in "0110_" und fuehren Sie erneut aus.
Ein häufiger Fehler
Warnung
Viele denken, die Maschine brauche Speicher für das Ergebnis neben dem Band. Das Band ist aber alles: Eingabe, Zwischenstand und Ergebnis. Ihr Gedächtnis ist unbegrenzt, weil das Band unendlich ist. Das unterscheidet sie vom endlichen Automaten, der nur Zustände hat.
Was eine Turingmaschine alles berechnen kann
Eine Turingmaschine kann beliebig weit zählen, vergleichen und kopieren. Damit erkennt sie auch Wörter, die kein Automat und keine Grammatik erkennt, etwa gleich viele a wie b mit einem dritten Zeichen dazwischen.
Nach dem Stand der Forschung lässt sich jedes Verfahren, das sich mit Stift und Papier ausführen lässt, als Turingmaschine schreiben. Das heißt Church-Turing-These. Ein Beweis ist sie nicht, aber bisher fand niemand ein Gegenbeispiel.
Ein Durchlauf des Kopfes im Terminal
Zwei Werkzeuge im Terminal verhalten sich wie sehr einfache Maschinen. tr ersetzt jedes Zeichen nach einer festen Regel, ein Kopf, der einmal von links nach rechts läuft. rev kehrt die Zeile um.
Der letzte Befehl rechnet Dezimalzahlen und dient als Kontrolle: Was steht nach dem Schritt 8 auf dem Band?
Jedes Bit umkehren
echo 1011 | tr 01 10Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Zeile umkehren
echo 1011 | revHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Kontrolle: 1011 plus eins
python3 -c "print(bin(int('1011', 2) + 1))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend
Entwerfen Sie eine Regeltabelle, die auf dem Band 111 ein 1 anhängt, also 1111 ergibt. Schreiben Sie drei Zustände auf.
Prüfen Sie sie danach mit Ihrer Funktion fuehre_aus.