Resource Bounds and Machine Invariance: Examples and Counterexamples

The polynomial $3n^2+5n+7$ is $O(n^2)$. So the hypothesis places $M$ in the setting of [L1] with $T(n)=n^2$.

Applying [L1] yields ${\mathrm{Space}}_M(n)=O(n^2)$. This matches the concrete intuition that a machine cannot visit more than a constant multiple of its own number of time steps.

The bit-doubling and pair-checking procedures are linear-time and linear-space translations between valid $\sigma$-codes and valid $\tau$-codes. Also $\mathrm{\mid }\tau (x)\mathrm{\mid }=2\mathrm{\mid }\sigma (x)\mathrm{\mid }$ for every instance $x$, so the two code lengths bound each other polynomially.

Therefore the hypotheses of [L1] hold, and [L1] transfers polynomial-time and polynomial-space decidability between the two tuple encodings.

On an input of length $n$, the two-tape presentation of $M$ ignores its second tape, makes one pass across the input on the first tape, and halts after a positive linear number $t(n)$ of steps.

Construct a one-tape machine $S$ by replacing each nonhalting transition of $M$ with three transitions. Before executing the original transition, $S$ moves one cell right without changing the scanned symbol, records in its finite control the original state and symbol together with the symbol seen on the right, then moves left while restoring that right-hand symbol, and finally performs the original transition. The two preliminary moves return the tape and head to their original state, so $S$ has exactly the same accept/reject behavior as $M$ but uses exactly $3t(n)$ steps on every length-$n$ input.

Since $t(n)>0$, the translated computation of $S$ and the original two-tape computation of $M$ have different exact step counts. Thus this translation is a counterexample to the false claim; [L1] is consistent with the witness because both running times remain linear.