8.5 Turing-Maschinen simulieren Turing-Maschinen: die universelle Turing-Maschine
Im letzten Teilkapitel haben wir gesehen, wie wir jede Turingmaschine $M$ mit Eingabealphabet $\Sigma$ codieren können als
$$
\begin{align*}
\enc(M) \in \Lambda^* \ ,
\end{align*}
$$
also als String über dem Codierungsalphabet
$$
\begin{align*}
\Lambda := \writelambda
\end{align*}
$$
Diese Codierungsschema enthält implizit Codierungsfunktionen $\enc_Q : Q \rightarrow \{0,1\}^+$ und $\enc_\Gamma: \Gamma \rightarrow \Sigma \cup \{0,1\}^+$, die wir verwenden, um die Zustände und Arbeitszeichen von $M$ in $\Lambda$ -Zeichen zu übersetzen. Für eine Konfiguration
$$
\begin{align*}
C = u_1 \dots u_m q v_1 \dots v_n
\end{align*}
$$
der Maschine $M$ definieren wir die Codierung von $C$ als
$$
\begin{align*}
\enc(C) := \enc_\Gamma(u_1) \texttt{#} \enc_\Gamma(u_2) \dots \texttt{#}
\enc_\Gamma(u_m)\texttt{#}
\enc_Q(q) \texttt{#} \enc_\Gamma(v_1)\texttt{#} \dots \texttt{#}
\enc_\Gamma(v_n) \in \Lambda^* \ .
\end{align*}
$$
Das ist alles nicht besonders tiefgründig und dient allein dazu, sicherzustellen, dass wir die Konfigurationen von $M$ darstellen können in dem Alphabet $\Lambda$, das unabhängig von $M$ ist. Dass wir also jede Turingmaschine $M$ mit Eingabealphabet $\Sigma$ und jede ihrer Konfigurationen als Strings über einem festen Alphabet $\Lambda$ darstellen können. Eine Turingmaschine simulieren heißt nun, einen String $\enc(M)\texttt{;}w$ mit $w \in \Sigma^*$ zu lesen und daraus den String $\enc(\hat{\delta}^*_M (w))$ zu berechnen, also das Ergebnis $\hat{\delta}^*_M(w)$, passend codiert über dem Alphabet $\Lambda$. 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 $\Sigma$ sei $\Lambda := \writelambda$ das Codierungsalphabet. Es gibt es eine Turingmaschine $U = U_{\Sigma}$ mit Eingabealphabet $\Lambda$, so dass für alle $c \in \Lambda^*$ und $w \in \Sigma^*$ die Turingmaschine $U$ mit Eingabewort $x \in \Lambda^*$ folgendes tut:
-
Falls $x$ nicht die Form $\enc(M) w$ mit $w \in \Sigma^*$ hat, lehnt sie ab;
-
Ansonsten, falls also $x = \enc(M)w$ für eine Turingmaschine $M$ und ein Wort $w \in \Sigma^*$ ist:
-
Falls $M$ mit Eingabewort $w$ nicht terminiert, dann terminiert $U$ mit Eingabewort $x$ auch nicht.
-
Falls $M$ mit Eingabewort $w$ eine Endkonfiguration $C = uqv$ erreicht, dann erreicht $U$ mit Eingabewort $x$ 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{align*}
\{ c w \ | \ w \in \Sigma^* \textnormal{ und } c = \enc(M) \textnormal{
und $M$ akzeptiert $w$} \} \ .
\end{align*}
$$
Ein technischer aber letztendlich irrelevanter Punkt: die Mengen $Q$ und $\Gamma$ der Turingmaschine $M$ können ja beliebige (endliche) Mengen sein, und weder $\Lambda$ noch die Turingmaschine $U$ haben "Kenntnis" von ihnen. Wir nehmen aber aus Gründen der Einfachheit an, dass $Q$ immer die Zustände $\qaccept$ und $\qreject$ enthält und auch $U$ diese Zustände verwendet. Daraus ergibt sich, dass für eine Endkonfiguration $uqv$ von $M$ zwar $q \in \{\qaccept, \qreject\}$ gilt, allerdings $\enc(q) \in \{0,1\}^+$, da wir diese $M$ -Zustände binär codieren. Somit ist $q\ \enc(uqv) \in \{\qaccept, \qreject\} \times \Lambda^*$ eine Endkonfiguration von $U$. Des weiteren gehen wir davon aus, dass das Blank-Symbol $\Box$ für alle Turingmaschinen $M$ mit Eingabealphabet $\Sigma$ das gleiche ist. Auch $U$ verwendet es. Wenn wir allerdings $M$ codieren, so wird auch $\Box$ als $\enc(\Box) \in \{0,1\}^+$ codiert, wie jedes Arbeitssymbol $z \in \Gamma \setminus \Sigma$ von $M$ binär codiert wird. Das heißt insbesondere, dass für eine $M$ -Konfiguration $C$ die Codierung $\enc(C)$ kein $\Box$ enthält (selbst wenn $C$ als Konfiguration von $M$ dies tut), und in der Tat ist ja $\enc(C) \in \Lambda^*$, und $\Lambda$ ist das Eingabealphabet von $U$ mit $\Box \not \in \Lambda$.
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.A\(\square\)
