Resource Bounds and Machine Invariance

For $n=0$ the claimed lower bound is immediate. For $n\ge 1$, the input head starts at cell $0$ and moves at most one cell per transition. Reaching cell $n-1$ therefore takes at least $n-1$ transitions. The hypothesis says the machine scans that cell before halting, so it must make a further transition from a nonhalting configuration scanning the cell before it can enter an accepting or rejecting state. Thus every such halting branch takes at least $n$ steps.

The hypothesis says this lower bound applies on every input of length $n$, and the input set is nonempty. By [L1], its worst-case maximum is at least the time on any one such input, so ${\mathrm{Time}}_M(n)\ge n$. Without the nonemptiness premise the claim fails for an empty input alphabet and $n>0$, because the revised worst-case convention gives value zero.

During one step, each of the $k$ heads can enter at most one new cell on its own tape. Therefore after $t$ steps, the total number of visited cells across all tapes is at most the initial $k$ cells plus $kt$. By [L1], every halting computation using $t$ steps uses at most $k(t+1)$ space.

If there are no length-$n$ inputs, the revised convention in [L1] makes both worst-case values zero. At an inhabited length, applying step 1.1 to the worst halting run gives ${\mathrm{Space}}_M(n)\le k({\mathrm{Time}}_M(n)+1)$. For sufficiently large inhabited lengths the hypothesis $T(n)\ge 1$ absorbs the additive constant, and [L2] converts the time bound into ${\mathrm{Space}}_M(n)=O(T(n))$.

By [L1], choose the one-tape simulator $S_M$ that reproduces the accept, reject, and divergence behavior of $M$ on every input.

For an input $w$ of length $n$, let $t={\mathrm{time}}_M(w)$. The quadratic-overhead lemma [L2] gives ${\mathrm{time}}_{S_M}(w)\le c_M(\mathrm{\mid }w\mathrm{\mid }+t+1{)}^2$ for a constant $c_M$ depending only on $M$. Because $t\le {\mathrm{Time}}_M(n)$ and $\mathrm{\mid }w\mathrm{\mid }=n$, the hypothesis and [L3] imply ${\mathrm{time}}_{S_M}(w)=O((n+T(n){)}^2)$. Taking the maximum over all $w$ of length $n$ yields ${\mathrm{Time}}_{S_M}(n)=O((n+T(n){)}^2)$.

The simulator from step 1.1 decides the same language as $M$, and step 2.1 gives the quantitative bound. Therefore the language decided by $M$ also lies in the one-tape deterministic time class described by [L4].

Use the standard simulator from [L1] that stores the $k$ simulated tapes as marked blocks on one tape. On an input of length $n$, the first simulated tape block initially records the whole input word, contributing $n$ cells up to a constant factor. Beyond that initial block, the simulator records only cells that the multitape computation has visited, together with only constant-size bookkeeping per recorded cell and a fixed number of delimiters depending on $M$. If the simulated computation has visited at most $S(n)$ cells altogether, [L2] therefore bounds the one-tape encoding length by $O(n+S(n))$.

Therefore there exists a constant $c_M$ such that every halting run of the simulator on an input of length $n$ visits at most $c_M(n+S(n)+1)$ cells. By [L3], this is $O(n+S(n))$. Taking maxima over all length-$n$ inputs gives ${\mathrm{Space}}_{S_M}(n)=O(n+S(n))$.

The simulator still decides the same language as $M$, and step 2.1 places it in the deterministic single-tape space class described by [L4].

By [L1], the simulator can first decode $e$ into the finite control data of $M$ and copy those data to a read-only program track. It then stores the current simulated configuration in a geometrically blocked tape layout whose block sizes double outward from the simulated heads. This representation keeps recently accessed cells near the center while allowing farther regions to be reached after only logarithmically many block crossings.

One simulated step of $M$ changes only the current state, one scanned tape symbol, and one head position. In the blocked layout from step 1.1, finding the current symbol, updating it, and recentering after a head move costs amortized $O_e(\log T)$ over the first $T$ simulated steps: most steps touch only the central blocks, and a level-$j$ reblocking costs $O_e(2^j)$ but occurs only once per $\mathrm{\Omega }(2^j)$ simulated head moves. Summing over the $O(\log T)$ occupied levels gives the asserted amortized bound. The subscript records the fixed cost of interpreting the finite alphabet, state set, and transition table encoded by $e$; the cited efficient-universality theorem permits exactly this machine dependence. No constructibility hypothesis on the integer $T$ is used.

Summing the amortized $O_e(\log T)$ cost over at most $T$ simulated steps gives total simulation time $O_e(T\log T)$. The initial decode-and-load work contributes $O_e(\mathrm{\mid }e\mathrm{\mid }+\mathrm{\mid }w\mathrm{\mid }+1)$. If the simulation halts with output word $u$, at most $\mathrm{\mid }w\mathrm{\mid }+T+1$ simulated tape cells can belong to its visited output segment. A final scan therefore converts $u$ to the self-delimiting word $\widehat{u}$ in $O_e(\mathrm{\mid }w\mathrm{\mid }+T+1)$ time, which is absorbed by the displayed bound. By [L2], the simulator is universal because it emits exactly $\widehat{u}$ and, when $M$ diverges, continues simulating forever rather than entering a halting state.

Therefore, for each fixed valid code $e$, the machine $U$ has the claimed universal behavior with total running time bounded by $c_e(\mathrm{\mid }e\mathrm{\mid }+\mathrm{\mid }w\mathrm{\mid }+T\log T+1)$ for a suitable constant $c_e$ independent of $w$ and $T$.

Suppose a language is decided by a deterministic multitape machine in time bounded by a polynomial $p(n)$. By [L1], there is a single-tape decider running in time $O((n+p(n){)}^2)$, and $(n+p(n){)}^2$ is still a polynomial. Thus polynomial time on multitape machines implies polynomial time on one tape.

Conversely, every one-tape machine is already a special case of a multitape machine, so any one-tape polynomial-time algorithm is automatically a multitape polynomial-time algorithm.

For space, [L2] shows that a multitape polynomial-space decider has a single-tape decider using $O(n+s(n))$ space, which is still polynomial whenever $s$ is polynomial. The reverse implication is immediate because one tape is a special multitape case.

Steps 1.1 and 1.2 prove model invariance for polynomial time, and step 1.3 proves it for polynomial space. Therefore the two standard models define the same polynomial-time and polynomial-space language classes.

On input $x$, the machine ${\mathrm{Clock}}_{e,t}$ first scans the whole input once to learn $\mathrm{\mid }x\mathrm{\mid }$. The lower bound hypothesis $n\le t(n)$ together with [L4] ensures that this preliminary scan fits inside the intended asymptotic budget. It then runs the constructor from [L1] on unary input $1^{\mathrm{\mid }x\mathrm{\mid }}$ to obtain the binary numeral of $t(\mathrm{\mid }x\mathrm{\mid })$ and writes a counter of that size on a work tape.

Next, using the fixed code $e$ from [L3], the machine initializes the simulated configuration of $M$ on $x$. It first checks whether that configuration is already halting. Otherwise, while the counter is positive it simulates one transition, decrements the counter, and checks whether the new configuration is halting. If so, it outputs exactly what $M$ outputs, including when this was the $t(\mathrm{\mid }x\mathrm{\mid })$-th transition. If the counter is zero and the simulated configuration is still nonhalting, it rejects. This is the standard clocked simulation built from the effective transition table [L3] and universal behavior in [L2].

Step 2.1 proves the two clauses of the statement: runs of $M$ halting in at most $t(\mathrm{\mid }x\mathrm{\mid })$ transitions are preserved, and overlong runs are cut off by a halting reject state.

Assume $L$ is decidable in polynomial time under $\tau$. Let $M_{\tau }$ be a decider for the code language $\tau [L]$ whose running time is polynomial in the input length. On an arbitrary binary input $z$, first run the assumed polynomial-time decider for the valid-code language $\sigma [I]$. If $z\mathrm{\notin }\sigma [I]$, reject. If $z=\sigma (x)$ is valid, compute $T_{\sigma \to \tau }(z)$ and run $M_{\tau }$ on that translated word. The output is correct because $T_{\sigma \to \tau }(\sigma (x))=\tau (x)$. By [L1] and [L2], the translated length is polynomially bounded in $\mathrm{\mid }z\mathrm{\mid }$, and the validity test and translator are polynomial-time by hypothesis, so the whole composition is polynomial-time.

The same composition argument works in the opposite direction using the validity test for $\tau [I]$ and the translator $T_{\tau \to \sigma }$. Therefore polynomial-time decidability under $\sigma$ and under $\tau$ are equivalent.

Replace the time bounds in step 1.1 by space bounds. The validity tests and translators use polynomial space by hypothesis, and [L1] again converts a polynomial bound in one encoding length into a polynomial bound in the other. Hence polynomial-space decidability is preserved in both directions as well.

Steps 2.1 and 2.2 prove the preservation of polynomial-time and polynomial-space classes described in [L3].

Let $M$ be a one-tape scanning machine, regarded by [L2] as a multitape machine with one tape. Translate it to an equivalent one-tape machine $S$ by inserting, before every original transition, a two-step right-then-left excursion that changes no tape symbol and records the finitely many encountered symbols in the control state. The third step performs the original transition. Thus $S$ has exactly the same behavior as $M$ but uses three steps for every nonhalting step of $M$.

On every input for which $M$ takes a positive number of steps, the translated computation takes three times as many, contradicting [A1]. This is consistent with [L1]: robustness preserves asymptotic complexity classes, not literal equality of running times.

Define the total bound $t(n):=2n+b(n)$ using [F1]. Then $t(n)\ge n$. If a uniform constructor could materialize $t(n)$ on input $1^n$, subtracting $2n$ from its output would compute $b(n)$, contradicting [F1]. Hence this total bound is not time-constructible in the sense of [L1].

The construction in [L2] works precisely by first computing the bound and then enforcing it as a timeout. Step 1.1 exhibits a total bound satisfying the size condition for which that first operation is impossible. Therefore [A1] is false: a uniform same-scale clock cannot be obtained for every total bound without a constructibility hypothesis.