Beweisidee. Die $k$-Band-Turingmaschine $M$, die $L$ entscheidet, macht auf Eingabe $x$ höchstens $T = t(|x|)$ Schritte. Es gibt also einen Bereich von insgesamt $2Tk$ Zellen ($2t$ pro Band), den sie nie verlässt. Das heißt, jede Konfiguration besteht aus $O(t)$ Zeichen.

Die Funktion $\hat{\delta}_M$, die für jede Konfiguration $C$ die Nachfolgekonfiguration $C' := \hat{\delta}_M(C)$ berechnet, ist sehr lokal und sehr einfach; die $i$-te Stelle von Konfiguration $C$ hat nur auf die Stellen $i-2$, $i-1$, $i$ und $i+1$ von $C'$ Einfluss. Somit können wir bei geeigneter binärer Codierung einen effizienten Schaltkreis bauen, der $\hat{\delta}_{M}$ berechnet.

Da wir wissen, dass $M$ höchstens $T$ Schritte macht, wissen wir, dass $\hat{\delta}^*(x) = \hat{\delta}^{(T)}(x)$ gilt; wir können nun einfach $T$ Schaltkreise hintereinanderschalten, um $\hat{\delta}^*(x)$ und somit die Endkonfiguration zu berechnen; mit einem weiteren einfachen Schaltkreis können wir nun den erreichten Endzustand auslesen und entsprechen 0 oder 1 ausgeben. \(\square\)

Beweis. Wir zeigen den Beweis schematisch anhand von $1$-Band-Turingmaschinen. Für $k$-Bandmaschinen geht es fast genau so. Erinnern Sie sich an die Definition der Konfiguration einer Turing-Maschine (). Formal war das ein Wort $C \in \Gamma^* \times Q \times \Gamma^*$. Ich zeige hier schematisch, wie aus einer Konfiguration per $\hat{\delta}$ die Folgekonfiguration wird:

Wenn also das Kopfsymbol an Stelle $i$ der Konfiguration steht, dann können sich in der Folgekonfiguration nur die Stellen $i-1$, $i$ und $i+1$ ändern. Allerdings hat bei einer Linksbewegung das gelesene Zeichen (an Stelle $i+1$) auch Einfluss auf den zukünftigen Inhalt von Zelle $i-1$; Zelle $j$ kann also Zellen $j-2, j-1, j, j+1$ im nächsten Schritt beeinflussen. Lege wir zuerst eine globale Indizierung der Stellen der Konfiguration fest. Der Schreib-Lese-Kopf startet an Zelle $0$ des Bandes; das Eingabewort belegt also die Zellen $0, 1, \dots, n-1$. Da die Turingmaschine maximal $T$ Schritte läuft, ist der Kopf immer auf einer Zelle in $\{-T, \dots, T\}$. Wir können also jede Konfiguration mit $2T+1$ Zeichen darstellen - nein, mit $S := 2T+2$ Zeichen, da der Kopf selbst ja auch eine Stelle der Konfiguration belegt. Somit ist also $C \in (Q \cup \Gamma)^{s}$. Unbenutzte Zellen links und rechts füllen wir mit $\Box$ auf, so dass immer eine Länge von $s$ benutzt wird.

Sei $C^{(t)} = \hat{\delta}^{(t)}(\qstart, x)$ die Konfiguration nach $t$ Schritten. Sei $C^{(t)}_i$ das $i$-te Zeichen darin. Den Wert von $C^{(t+1)}_i$ können wir bestimmen allein mit Kenntnis von $C^{(t)}_{i-1}$, $C^{(t)}_{i}$, $C^{(t)}_{i+1}$ und $C^{(t)}_{i+2}$. Es gibt also eine Funktion

\begin{align*} \tilde{\delta} : (Q \cup \Gamma)^4 \rightarrow (Q \cup \Gamma) \end{align*}

die dies beschreibt, also mit

\begin{align*} C^{(t+1)}_i & = \tilde{\delta} \left(C^{(t)}_{i-1}, C^{(t)}_{i}, C^{(t)}_{i+1},C^{(t)}_{i+2}\right) \ . \end{align*}

Im Detail ist die Arbeitsweise von $\tilde{\delta}$ wie folgt:

\begin{align*} \tilde{\delta}(a,x,y,*) & = x \quad \textnormal{falls $a, x, y \in \Gamma$}\\ \tilde{\delta}(a,x,q,y) & = \begin{cases} r & \textnormal{falls $\delta(q,y) = (r,*,L)$} \\ x & \textnormal{sonst.} \end{cases}\\ \tilde{\delta}(x,q,y,*) & = \begin{cases} x & \textnormal{ falls $\delta(q,y) = (*, *, L)$ } \\ r & \textnormal{ falls $\delta(q,y) = (r, *, S)$ } \\ z & \textnormal{ falls $\delta(q,y) = (*, z, R)$ } \ \end{cases}\\ \tilde{\delta}(q,y,*,*) & = \begin{cases} r & \textnormal{ falls $\delta(q,y) = (r, *, R)$} \\ z & \textnormal{ falls $\delta(q,y) = (*, z, S)$} \\ z & \textnormal{ falls $\delta(q,y) = (*, z, L)$} \\ \end{cases} \end{align*}

Wenn wir $Q \cup \Gamma$ binär codieren mit $l := \ceil{\log_2 |Q \cup \Gamma|}$ Bits, so wird $\tilde{\delta}$ zu einer Booleschen Funktion $\tilde{\delta} : \{0,1\}^{4l} \rightarrow \{0,1\}^l$. Wir können dafür einen Schaltkreis der Größe $O(2^l) = O(|\Gamma \cup Q|^4)$ bauen: per Wahrheitstabelle wird er etwas größer; mit der Lupanov-Schranke () kriegen Sie $O(2^l)$.

Wir haben nun also einen Schaltkreis $\Delta$, der $\tilde{\delta}$ berechnet. Seine Größe ist $O(|\Gamma \cup Q|^4)$. Da wir $|Q|$ und $|\Gamma|$ als konstant betrachten, da es nicht von der Eingabegröße $n=|x|$ abhängt, können wir sogar behaupten: die Größe von $\Delta$ ist $O(1)$. Wir schalten jetzt $S$ Kopien von $\Delta$ parallel, um $\hat{\delta}: \mathcal{C} \rightarrow \mathcal{C}$ zu berechnen, also aus einer gegebenen Konfiguration die Folgekonfiguration:

Jeder Pfeil steht hierbei für $l$ Boolesche Kabel. Dies ergibt einen Schaltkreis $\Delta^S$, der $\hat{\delta}: \mathcal{C} \rightarrow \mathcal{C}$ berechnet (bzw. die Boolesche Codierung dieser Funktion) und Größe $O(S) = O(t(n))$ hat:

Die Inputs, die Zellen außerhalb des Bereichs lesen, setzen wir einfach auf $\Box$ (Blank) bzw. dessen binäre Codierung, weil wir ja wissen, dass der Schreib-Lese-Kopf niemals dorthin gelangen wird. Jetzt schalten wir $T$ Kopien von $\Delta^{S}$ hintereinander, um aus der Startkonfiguration $C^{(0)}$ die Endkonfiguration $C^{(T)}$ zu berechnen:

Ganz zum Schluss bauen wir uns noch einen Schaltkreis, der an jede Stelle von $C{^(T)}$ schaut und, falls dort der Endzustand steht, liest, ob das accept oder reject ist und je nachdem $1$ oder $0$ ausgibt.

Dieser endgültige Schaltkreis besteht im Wesentlichen aus $T$ Kopien von $\Delta^S$ und hat somit Größe $O(t(n)^2)$. \(\square\)