Turing-Maschinen

Lernziele

• Du kannst beschreiben, wie eine Turing-Maschine aufgebaut ist und was sie von einem endlichen Automaten unterscheidet.
• Du kannst ein einfaches Turing-Programm Schritt für Schritt nachvollziehen.
• Du kennst die Bedeutung der Turing-Maschine für die Frage, was «berechenbar» heisst.

Die Idee

1936 — es gab noch keine Computer — stellte sich Alan Turing die Frage: Was heisst es eigentlich, etwas zu berechnen? Seine Antwort war eine gedachte Maschine, so einfach wie möglich, aber so stark wie nötig.

Eine Turing-Maschine besteht aus:

• einem Band, unendlich lang, unterteilt in Felder. Jedes Feld enthält ein Zeichen oder ist leer.
• einem Kopf, der auf genau einem Feld steht. Er kann das Zeichen dort lesen und überschreiben und sich um ein Feld nach links oder rechts bewegen.
• einer Steuerung mit endlich vielen Zuständen — das ist genau unser endlicher Automat von vorher.

Der entscheidende Unterschied zum endlichen Automaten: Die Turing-Maschine kann auf das Band schreiben und sich darauf frei bewegen. Das Band ist ihr Gedächtnis, und es ist unbeschränkt. Damit kann sie zählen — und viel mehr.

Ein Schritt der Maschine

In jedem Schritt schaut die Maschine auf zwei Dinge: ihren aktuellen Zustand und das Zeichen unter dem Kopf. Daraus ergibt sich, was sie tut:

1. ein Zeichen aufs aktuelle Feld schreiben (oder das alte stehen lassen),
2. den Kopf nach links oder rechts bewegen,
3. in einen neuen Zustand wechseln.

Das war's. Eine Regel notieren wir so:

$(\text{Zustand},\ \text{gelesen}) \rightarrow (\text{geschrieben},\ \text{Richtung},\ \text{neuer Zustand})$

Beispiel: Invertieren

Auf dem Band steht ein Wort aus 0 und 1, der Kopf steht auf dem ersten Zeichen. Die Maschine soll jedes Zeichen umdrehen: aus 0 wird 1, aus 1 wird 0. Zwei Regeln reichen, plus eine fürs Anhalten:

Verfolge es für 101 von Hand: Die Maschine schreibt 0, geht nach rechts, schreibt 1, geht nach rechts, schreibt 0, geht nach rechts, sieht ein leeres Feld und hält. Auf dem Band steht 010.

Eine Turing-Maschine in Python

Auch eine Turing-Maschine passt in wenige Zeilen Python. Das Band ist eine Liste, die Regeln sind ein Dictionary:

regeln = {
    ("los", "0"): ("1", +1, "los"),
    ("los", "1"): ("0", +1, "los"),
    ("los", " "): (" ",  0, "stopp"),
}

def turing(band):
    band = list(band) + [" "]
    kopf = 0
    zustand = "los"
    while zustand != "stopp":
        schreiben, richtung, zustand = regeln[(zustand, band[kopf])]
        band[kopf] = schreiben
        kopf += richtung
    return "".join(band).strip()

print(turing("101"))

Aufgabe: Plus eins im Binärsystem

Diese Maschine soll zu einer Binärzahl 1 addieren, z.B. 1011 → 1100. Idee: Der Kopf läuft zuerst ganz nach rechts (Zustand suche), dann von rechts nach links (Zustand addiere): Eine 0 wird zur 1 — fertig. Eine 1 wird zur 0 — Übertrag, weiter nach links.Vervollständige die Regeln für den Zustand addiere.

regeln = {
    ("suche", "0"): ("0", +1, "suche"),
    ("suche", "1"): ("1", +1, "suche"),
    ("suche", " "): (" ", -1, "addiere"),
    # ergänze: was macht "addiere" bei "0", "1" und " "?
    # Tipp: bei " " (linker Rand erreicht) eine "1" schreiben und stoppen.
}

def turing(band):
    band = [" "] + list(band) + [" "]
    kopf = 1
    zustand = "suche"
    while zustand != "stopp":
        schreiben, richtung, zustand = regeln[(zustand, band[kopf])]
        band[kopf] = schreiben
        kopf += richtung
    return "".join(band).strip()

print(turing("1011"))  # sollte 1100 ergeben

Warum diese Maschine so wichtig ist

Die Turing-Maschine wirkt primitiv. Aber: Alles, was ein heutiger Computer berechnen kann, kann auch eine Turing-Maschine berechnen — nur langsamer. Jede Programmiersprache, jeder Prozessor, jedes KI-Modell lässt sich im Prinzip auf diese eine Maschine zurückführen.

Die Church-Turing-These sagt: «Berechenbar» heisst genau «von einer Turing-Maschine berechenbar». Das ist keine bewiesene Aussage, sondern eine Definition dessen, was Berechnung bedeutet — und in 90 Jahren hat niemand ein Gegenbeispiel gefunden.

Und das Beste: Weil die Maschine so einfach ist, kann man über sie beweisen, was Computer grundsätzlich nicht können. Das schauen wir auf der nächsten Seite an.

Kurz geprüft