Satz Anzahl der Konfiguration einer ROITM

Einfache Sprache

Def. Konfiguration einer ROITM

Sei $\mathcal M$ eine ROITM und $w$ eine Eingabe. Dann besteht die Konfiguration von $\mathcal M$ auf $w$ aus dessen Zustand, dem Arbeitsband, und Position der Zwei Lese-Schreib-Köpfe. Bemerke, dass die Eingabe $w$ auf dem Eingabeband nicht Teil der Konfiguration von $\mathcal M$ auf $w$ ist.

Falls $\mathcal M$ eine Platzkomplexität von $f(n)$ hat und $w$ eine Eingabe der Lände $n$ ist, dann ist die Anzahl der Konfigurationen von $\mathcal M$ auf $w$ genau $n2^{O(f(n))}$.

Beweis: Nehme an das $\mathcal M$ $c$ Zustände und $g$ Bandsymbole hat. Die Anzahl der Strings die auf dem Arbeitsband erscheinen können ist $g^{f(n)}$. Die Lese-Schreibköpfe kann bzgl. des Eingabebandes in $n$ verschiedenen Positionen sein und bzgl. des Arbeitsbandes in $f(n)$ Positionen. Zusammen ergibt das $cnf(n)g^{f(n)}$ oder