8.5 Turing-Maschinen simulieren Turing-Maschinen: die universelle Turing-Maschine

Im letzten Teilkapitel haben wir gesehen, wie wir jede Turingmaschine $M$ mit Eingabealphabet $Σ$ codieren können als

\begin{array}{r} enc (M) \in Λ^{*}, \end{array}

also als String über dem Codierungsalphabet

\begin{array}{r} Λ := Σ \cup {0, 1, #,,, L, S, R,;} \end{array}

Diese Codierungsschema enthält implizit Codierungsfunktionen ${enc}_{Q} : Q \to {0, 1}^{+}$ und ${enc}_{Γ} : Γ \to Σ \cup {0, 1}^{+}$ , die wir verwenden, um die Zustände und Arbeitszeichen von $M$ in $Λ$ -Zeichen zu übersetzen. Für eine Konfiguration

\begin{array}{r} C = u_{1} \dots u_{m} q v_{1} \dots v_{n} \end{array}

der Maschine $M$ definieren wir die Codierung von $C$ als

\begin{array}{r} enc (C) := {enc}_{Γ} (u_{1}) # {enc}_{Γ} (u_{2}) \dots # {enc}_{Γ} (u_{m}) # {enc}_{Q} (q) # {enc}_{Γ} (v_{1}) # \dots # {enc}_{Γ} (v_{n}) \in Λ^{*} . \end{array}

Das ist alles nicht besonders tiefgründig und dient allein dazu, sicherzustellen, dass wir die Konfigurationen von $M$ darstellen können in dem Alphabet $Λ$ , das unabhängig von $M$ ist. Dass wir also jede Turingmaschine $M$ mit Eingabealphabet $Σ$ und jede ihrer Konfigurationen als Strings über einem festen Alphabet $Λ$ darstellen können.

Eine Turingmaschine simulieren heißt nun, einen String $enc (M); w$ mit $w \in Σ^{*}$ zu lesen und daraus den String $enc ({\hat{δ}}_{M}^{*} (w))$ zu berechnen, also das Ergebnis ${\hat{δ}}_{M}^{*} (w)$ , passend codiert über dem Alphabet $Λ$ . Das zentrale Ergebnis dieses Teilkapitels ist, dass wir diese Simulation selbst mit einer Turingmaschine implementieren können.

Theorem 8.5.1 (Universelle Turingmaschine). Zu jedem endlichen Eingabealphabet $Σ$ sei $Λ := Σ \cup {0, 1, #,,, L, S, R,;}$ das Codierungsalphabet. Es gibt es eine Turingmaschine $U = U_{Σ}$ mit Eingabealphabet $Λ$ , so dass für alle $c \in Λ^{*}$ und $w \in Σ^{*}$ die Turingmaschine $U$ mit Eingabewort $x \in Λ^{*}$ folgendes tut:

Falls $x$ nicht die Form $enc (M); w$ mit $w \in Σ^{*}$ hat, lehnt sie ab;
Ansonsten, falls also $c = enc (M)$ für eine Turingmaschine $M$ ist:
- Falls $M$ mit Eingabewort $w$ nicht terminiert, dann terminiert $U$ mit Eingabewort $c; w$ auch nicht.
- Falls $M$ mit Eingabewort $w$ eine Endkonfiguration $C = u q v$ erreicht, dann erreicht $U$ mit Eingabewort $c; w$ die Endkonfiguration $q enc (C)$ . Das heißt insbesondere, dass $U$ genau dann akzeptiert, wenn $M$ akzeptiert, und genau dann ablehnt, wenn $M$ ablehnt.

$U$ akzeptiert also die Sprache

\begin{array}{r} {c w | w \in Σ^{*} und c = enc (M) und M akzeptiert w} . \end{array}

Ein technischer aber letztendlich irrelevanter Punkt: die Mengen $Q$ und $Γ$ der Turingmaschine $M$ können ja beliebige (endliche) Mengen sein, und weder $Λ$ noch die Turingmaschine $U$ haben "Kenntnis" von ihnen. Wir nehmen aber aus Gründen der Einfachheit an, dass $Q$ immer die Zustände $q_{y e s}$ und $q_{n o}$ enthält und auch $U$ diese Zustände verwendet. Daraus ergibt sich, dass für eine Endkonfiguration $u q v$ von $M$ zwar $q \in {q_{y e s}, q_{n o}}$ gilt, allerdings $enc (q) \in {0, 1}^{+}$ , da wir diese $M$ -Zustände binär codieren. Somit ist $q enc (u q v) \in {q_{y e s}, q_{n o}} \times Λ^{*}$ eine Endkonfiguration von $U$ .

Des weiteren gehen wir davon aus, dass das Blank-Symbol $◻$ für alle Turingmaschinen $M$ mit Eingabealphabet $Σ$ das gleiche ist. Auch $U$ verwendet es. Wenn wir allerdings $M$ codieren, so wird auch $◻$ als $enc (◻) \in {0, 1}^{+}$ codiert, wie jedes Arbeitssymbol $z \in Γ ∖ Σ$ von $M$ binär codiert wird. Das heißt insbesondere, dass für eine $M$ -Konfiguration $C$ die Codierung $enc (C)$ kein $◻$ enthält (selbst wenn $C$ als Konfiguration von $M$ dies tut), und in der Tat ist ja $enc (C) \in Λ^{*}$ , und $Λ$ ist das Eingabealphabet von $U$ mit $◻ \notin Λ$ .

Beweis. Den Beweis in allen Details zu führen hieße, die Maschine $U$ konkret als Turingmaschine zu implementieren. Wir tun dies nicht. Wir beschränken uns auf eine High-Level-Beschreibung ihrer Arbeitsweise.