Satz Laufzeit zusätzlicher Bänder

Einfache Sprache

Def. Satz Laufzeit zusätzlicher Bänder

Sei $t(n)$ eine Funktion mit $t(n)\geq n$. Dann hat jede $t(n)$ Laufzeit k-Band TM eine äquivalente $O(t^2(n))$ Laufzeit TM.

Idee: Wir nutzen die Konstruktion aus dem Satz Redundanz zusätzlicher Bänder und bestimmen dessen Zeitkomplexität. Dabei wird klar das für die Simulation eines Schrittes der k-Band TM höchstens $O(t(n))$ Zeit benötigt wird. Da höchstens $O(t(n))$ Schritte simuliert werden müssen, ergibt das eine gesamt Laufzeit von $O(t^2(n))$

Beweis: Sei $M$ eine k-Band TM mit Zeitkomplexität $O(t(n))$. Sei $S$ die TM die nach dem Satz Redundanz zusätzlicher Bänder existiert. $\left[\mathrm{Z\kern-.5em\raise-0.6ex\hbox{Z}}\; S \in O(t^2(n))\right]$ Um einen Schritt von $M$ zu simulieren muss $S$ einmal über das ganze Band fahren um herauszufinden, welches Symbol unter jedem Lese-/Schreibkopf ist. Dann muss $M$ noch einmal über das ganze Band fahren um die die einzelnen Stellen wo sich die Lese-/Schreibköpfe befinden zu aktualisieren. Falls ein Lese-/Schreibkopf mehr Platz benötigt dann wird der Rest nach Rechts verschoben. Die Länge des Bands ist also entscheidend für die Laufzeit. Jedes Band von $M$ hat höchstens eine Länge von $t(n)$. Alles zusammen braucht $S$ also für eine Fahrt über das Band $O(t(n))$ Schritte. Für jeden Schritt von $M$ muss $S$ also 2 mal über das Band fahren und höchstens $k$ mal das Band nach rechts verschieben. Also $O(t(n))$. Zu beginn muss $S$ die Eingabe von $M$ in dem richtigen Format auf das Band schreiben. Das brauch $O(t(n))$. Dann müssen wir für jeden der $t(n)$ Schritte die $M$ läuft $O(t(n))$ Schritte in der $S$ laufen. Für die Simulation ergibt das $t(n)\times O(t(n)) = O(t^2(n))$ Schritte. Insgesamt haben wir also $O(t(n))+O(t^2(n))$ Schritte. Wir nehmen an, dass $t(n)\geq n$. Es folgt, dass $S\in O(t^2(n))$.