Time and Space Hierarchy Theorems

Parse $z$ into three self-delimiting fields for a machine code, a canonical positive binary integer $c$, and an ignored padding string, rejecting trailing data. Use the finite-table multitape extension in An efficient universal simulation with a clock of the total decoder in A fixed effective binary encoding of deterministic one-tape Turing machines. Invalid fields return the fixed rejector pair with multiplier one. Every finite string is thereby decoded in finite time; listing all strings in length-lexicographic order gives the enumeration.

For each valid machine and multiplier, encoding these fields with successively longer padding supplies arbitrarily long codes for that pair. On input $x$, compute $b=ch(\mathrm{\mid }x\mathrm{\mid })$ using the fixed halting constructor. A step counter enforces $b$ simulated transitions, returning a halting result if it occurs within the budget and otherwise rejecting. This is the supplied step-clock interface.

For a cell cap, maintain the minimum and maximum visited position on each simulated tape, together with their total interval length. Each tape head moves to an adjacent cell, so these intervals count precisely its visited cells. Include the initial visited cells, rejecting immediately if they already exceed $b$, and reject before a transition that would enlarge the total beyond $b$. This effective monitor preserves every run staying within the cap; a loop inside it may continue forever. A separate configuration clock is needed to force such a run to halt.

If the relevant resource use of $M$ is $O(h(n))$, some fixed positive integer $c$ bounds it for all sufficiently large $n$. The enumeration includes this pair, and its corresponding monitor then preserves those computations. No claim about exceptional small lengths where $h(n)=0$, or about the monitor's own resource overhead, is implicit.

Define one fixed multitape procedure $R$ on $w$: decode $(M,c)$, reject malformed codes, construct the binary value $cf(n)$ for $n=\mathrm{\mid }w\mathrm{\mid }$, and run the time interpreter $U_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}$ from Clocked universal simulation with time and space bounds on $M$ with simulated input equal to the entire word $w$. If the inner simulation returns, output the opposite of its result. This is a fixed interpreter; its decoding, clock construction, and universal-simulator transitions are all actual transitions of $R$.

The diagonal decider first computes $g(n)$ and constructs a unary timer of that length. The constructor costs $O(n+g(n))$. Converting its binary output to unary also costs $O(g(n)+\log (g(n)+2))$: repeatedly decrement a least-significant-bit-first counter and emit a mark, charging the traversed carry/borrow runs over the whole countdown. Their total is linear in the initial counter value. Rewind the timer, then execute $R$ with its fixed tapes and one additional timer tape. Each simulated transition of this fixed $R$ advances the timer once; at its end output a default rejection unless $R$ has already returned. The fixed transition table is incorporated directly, so this outer clock adds constant overhead per transition, not another universal-simulation factor.

On every input, including malformed descriptions and arbitrarily large encoded multipliers, the outer clock permits at most $g(n)$ transitions of $R$. All input-dependent decoding and inner-clock work are inside that clock. Thus total time is $O(n+g(n))=O(g(n))$, after treating finitely many lengths below the eventual floor separately.

Fix $(M,c)$. On its valid padded codes, decoding and copying the full simulated input cost $O_{M,c}(n)$; constructing the inner clock costs $O_c(n+f(n))$. The proved time clause of Clocked universal simulation with time and space bounds gives $O_M(n+cf(n)\log (cf(n)+2))$ for the supplied binary clock. For this fixed pair the combined runtime of $R$ is $O_{M,c}(n+f(n)\log (f(n)+2))=o(g(n))$. It therefore finishes before the outer timer on every sufficiently long code of that pair. Arbitrarily long such codes exist by the enumeration, and the returned answer is the required complement.

Apply [L1] to obtain its language $D\in \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$.

Since $f(n)$ is eventually at least $n$ and $f(n)\log f(n)=o(g(n))$, we have $f(n)=O(g(n))$. Any $O(f)$ decider is therefore also an $O(g)$ decider, proving $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)\subseteq \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$.

Suppose a machine $M$ running in $O(f)$ decided $D$. Fix an integer $c$ large enough to bound its running time by $cf(n)$ at all sufficiently large $n$; enlarge $c$ to cover the finitely many shorter lengths as well. By [L1], the clocked pair $(M,c)$ has arbitrarily long valid padded codes $w$, and on each sufficiently long one the diagonal decider returns the complement of $M(w)$, since the inner clock does not expire. But $M$ decides $D$ on $w$, a contradiction. Thus $D\mathrm{\notin }\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$; combine this with steps 1.1–1.2 for strict containment.

A fixed transducer reads $1^n$, counts $n$, finds $k=\lceil \sqrt{n}\rceil$ by integer search for the least $k$ with $k^2\ge n$, and writes the binary word $1$ followed by $k$ zeros. For the finitely many lengths where $n+1>2^k$, a literal branch instead writes $\mathrm{bin}(n+1)$. Its time is polynomial in $n$ plus $O(k)$, hence $O(f(n))$, since every fixed polynomial in $n$ is eventually below $2^{\sqrt{n}}$. A second transducer reads $1^n$ and writes $1$ followed by $n$ zeros in $O(n+1)=O(2^n)$ time. Both fully read the input and $f,g\ge n+1$, so they are time constructible in the stated output sense. Every polynomial is $O(f)$ because $d{\log }_{2}n=o(\sqrt{n})$ for each fixed exponent $d$, and $f\log f=o(g)$ because $\sqrt{n}+{\log }_2(\sqrt{n}+1)=o(n)$.

The deterministic time hierarchy applied to step 1.1 gives $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)⊊\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$. Since $P\subseteq \mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$ and $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)\subseteq EXP$, it supplies a language in $EXP\setminus P$.

Construct a deterministic unary-input clock as follows: read its input, compute the binary value $g(n)$ with the fixed constructor, and perform $g(n)$ countdown iterations before halting. A least-significant-bit-first binary counter has linear total decrement cost (the numbers of bit changes form a geometric sum); returning its head after each decrement has the same bound. Thus the clock's actual running time $T(n)$ is $\mathrm{\Theta }(g(n))$ eventually, and can be arranged to be at least $n$ for every $n$. It is an exact running time in the terminology of Seiferas--Fischer--Meyer, even though $g$ was supplied only by an asymptotically bounded binary-output constructor.

Apply Nondeterministic recursive-padding separation to the exact clock $T$ from step 1.1. It gives a binary language $D\in \mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(T)$ under the local all-branch convention, but $D\mathrm{\notin }\mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(a)$ for every total recursive $a\ge n$ with $a(n+1)=o(T(n))$.

Since $T(n)=O(g(n))$, the all-branch $O(T)$ machine from step 2.1 is an all-branch $O(g)$ machine. Hence $D\in \mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$.

If $D$ belonged to local $\mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$, a constant integer $C$ would bound its accepting times at every length by the total recursive function $a(n)=\max \{n,Cf(n),C\}$: enlarge $C$ to cover the finitely many exceptional lengths. Since $f(n)\ge n$ eventually, $a(n+1)=O(f(n+1))=o(g(n))=o(T(n))$. This contradicts the exclusion in step 2.1. Thus $D\mathrm{\notin }\mathrm{N}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$.

Nondecreasing $f$ gives $f(n)\le f(n+1)=o(g(n))$, so every all-branch $O(f)$ decider is an all-branch $O(g)$ decider. Together with steps 3.1 and 3.2 this proves the strict inclusion.

Decode and retain the description and input using $O(n)$ space. Write $b=\lceil {\log }_2(\mathrm{\mid }{\mathrm{\Gamma }}_M\mathrm{\mid }+1)\rceil$. Represent each simulated tape by the consecutive cells from its left boundary to its furthest visited cell, storing a $b$-bit symbol and a head-marker bit in each cell block. Separate tapes by delimiters. Every tape has at least its initial cell visited, so their number is at most $S$. Store the current state by its binary index, of length at most $n$. Unvisited input symbols can be recovered from the retained input when a tape block first reaches them. Thus the complete representation has length $O(n+Sb)$.

For a simulated transition, scan the tape blocks to collect the marked symbols, look up the unique matching transition in the retained explicit table, and scan again to update symbols and markers. Keep old and new marker tracks distinct until the update is finished, so a head moving along a sweep is updated only once. A new rightmost cell is appended when necessary; at a left boundary clamp a left move. The scanned-symbol tuple and update tuple use $O(Sb+n)$ bits, and counters or copies of the current representation use at most the same order. Reuse all scratch after each update. Induction on simulated transitions gives the correct represented configuration at each completed update, without retaining the history.

This is an algorithm on a fixed finite alphabet and a fixed finite number of simulator tapes: variable simulated tape blocks reside on those tapes as delimited data. Every stage uses $O(n+Sb)$ cells, with a constant independent of $M$. For fixed $M$, $b$ is constant, giving $O_M(n+S)$; if the alphabet is fixed in advance, the same constant works uniformly for its machines.

To cap the encoding, maintain a binary counter for the number of cells allocated to its tapes, including update scratch, and abort before that count exceeds $B$. The counter and supplied binary limit use $O(\log (B+2))$ additional cells, so the bounded version uses $O(n+B+1)$ space. For each fixed $M$ there is a constant $C_M$ bounding all workspace in steps 1.1--2.1 by $C_M(n+S)$; when $n+S=o(B)$ this lies below $B$ eventually. Hence the cap does not truncate those simulations.

Determine $n$, form $1^n$, and run the constructor to obtain $B=s(n)$. This halts and uses $O(n+s(n))=O(s(n))$ space. Thereafter use the fixed capped simulator, excluding the timeout counter for now. Its coded input and binary bound, cap bookkeeping, representation, and scratch fit in $K=C(n+B+1)$ cells for a fixed integer $C$, by the simulator's cap interface. The integer $K$ itself can be computed in $O(n+B+1)$ space.

Let $q,k,a$ be respectively the number of states, tapes, and tape symbols of this fixed capped simulator. On its fixed input, each head is in a position below $K+1$, and each tape can be represented by its first $K+1$ symbols; all later input symbols are fixed and all later work symbols are blank. Thus it has at most $q(K+1{)}^k{a}^{k(K+1)}$ configurations. Since $K\ge 1$ and $K+1\le 2^K$, fix an integer $d$ large enough that this number is strictly below $2^{dK}$ for every $K\ge 1$. All these constants belong to the fixed simulator, independently of the decoded adversary.

Simulate at most $2^{dK}$ transitions of that capped simulator, checking halting or a cap abort at every stage. A binary counter of $dK+1$ bits suffices. If a deterministic computation repeats a configuration, its future repeats and it cannot first halt later. Consequently any halting capped computation halts before this clock expires; otherwise the procedure returns its default answer. This counts transitions of the fixed simulator itself, including its scans and scratch updates, rather than transitions of the decoded machine.

The constructor halts by hypothesis, and the later clock forces termination. Its counter uses $O(K)=O(n+s(n))=O(s(n))$ cells, as do the capped simulation and retained input. Therefore the resulting diagonal procedure is total in the asserted space, preserving every non-aborted simulated halting answer for inversion.

Define a diagonal decider $D$ on strings $z=1^{\mathrm{\mid }e\mathrm{\mid }}0e{01}^k$, where $e$ is a valid finite machine description and $k\ge 0$. Reject malformed strings. On a valid string of length $n$, compute $g(n)$ using its fixed constructor and simulate the described machine $M$ on the entire original string $z$, capping all encoded simulation and scratch at $B=\max \{1,g(n)\}$. The parser and any coded description/input copy cost $O(n)$ space. Use [L2] with the size of this fixed capped simulator's actual storage, which is $O(n+B)$, to force halting; on cap overflow or timeout reject, and on simulated halting return the opposite answer. The constructor costs $O(g(n))$, and $n=O(f(n))$ with $f=o(g)$ implies $n=O(g(n))$. Hence $D$ is a total $O(g(n))$-space decider.

Suppose a fixed machine $M$ decides the language of $D$ in at most $cf(n)$ cells for sufficiently large $n$. For its fixed description $e$, the strings in step 1.1 exist at every sufficiently large length. The space needed for faithful simulation is $O_M(n+cf(n))=o(g(n))$, so sufficiently long such strings do not trigger the encoded cap. Since $M$ halts, [L2] also guarantees that the timeout does not prevent its answer. On such a string $z$, $D(z)$ is therefore the opposite of $M(z)$, a contradiction. Thus the language of $D$ is outside $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f)$, while step 1.1 puts it in $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g)$. Finally $f=O(g)$ gives the ordinary class inclusion.

Read the machine and input as two delimited regions of the one read-only input $z$. Store their endpoints and the simulated input-head address in $O(\log (n+2))$ bits; the simulated input is endmarked and confined to its field. The effective finite-table coding underlying Effective enumeration of clocked machines applies also with one input tape designated read-only. Table fields and transition entries can be found by rescanning rather than copying the program.

For fixed $M$, store the work tapes as finite words with marked heads and interval endpoints. Its alphabet and tape count are constants, so a run using at most $b$ work cells has an encoding of length $O_M(b+1)$. Work-head addresses and the visited-cell counter add $O_M(\log (b+2))$ bits, and the finite-control encoding is constant. Before extending a visited interval, test the cell cap and reject on overflow, including an initial overflow. A binary cap itself uses $O(\log (b+2))$ bits. Thus the work bound is $O_M(b+\log (n+2))$.

Alternatively, count actual visited work cells in the simulator's binary representation, including configuration, cap, and scratch storage; enforce the encoded-storage limit before each visit to a new work cell. The input-field addresses and allocation counter need only $O(\log (n+2)+\log (b+2))$ auxiliary bits. Program lookup can compare indexed table fields by repeated scans in $O(\log (n+2))$ space. Reject malformed codes or an overflow. This gives the uniform bound, with faithful transition simulation whenever all required storage fits. Large alphabets or many tapes may trigger this guard even if the simulated cell count is at most $b$.

In either version, each completed simulated transition is exactly the transition selected by the encoded table, so induction gives faithfulness up to halting or overflow. No configuration-time counter was introduced, and thus within-cap loops are not falsely declared halting. The logarithmic floor absorbs the address term in each respective bound.

Compute $s(n)$ in $O(s(n))$ work space, simulating the constructibility machine on a virtual unary input of length $n$ if necessary. For varying descriptions, reject when the universal simulator's entire encoded configuration and scratch storage would exceed $s(n)$ cells. A configuration below this cap is described by $O(s(n))$ bits, together with $O(\log (n+2))$ bits for input and program addresses. Thus the number of possible configurations is at most $2^{O(s(n)+\log (n+2))}=2^{O(s(n))}$. The cap may reject a computation before this bound is reached.

Use the uniform encoded-storage simulator and a binary counter of $O(s(n))$ bits to count through this configuration bound, stopping at expiry or an earlier storage overflow. A deterministic computation that remains within the cap and has not halted by then must repeat a configuration. The forced answer therefore makes the simulation total while the simulator, counter, and address bookkeeping together use $O(s(n))$ work space. For a fixed machine the visited-cell version of the supplier gives the analogous bound.

Define a diagonal decider $D$ on an input string $z$ of length $n$. Compute $g(n)$ with its fixed read-only work-space constructor, presenting a virtual unary input $1^n$ using the known input length. Decode $z$ as a padded machine code using Effective enumeration of clocked machines, interpreting valid codes for read-only-input deciders and rejecting malformed or other codes. The decoded program is read by rescanning its field in $z$; the simulated input is the entire original string $z$. Set $b=\lfloor g(n)\mathrm{/}4\rfloor$. If $b=0$, return a fixed answer. Otherwise run the uniform encoded-storage simulator of Universal simulation preserves read-only work space up to constants with cap $b$, rejecting before its encoded configuration or scratch storage exceeds that cap. Include the simulator's input/program addresses and cap bookkeeping in the charged storage. Stop the simulation after its finite configuration bound as in The read-only-workspace diagonal machine halts. If it halted within the cap, return the opposite answer; on overflow or clock expiry, return a fixed answer.

The constructor uses $O(g(n))$ work cells. Program decoding and rescanning need $O(\log (n+2))$ addresses; the uniform simulator uses at most $b$ charged encoded cells plus $O(\log (n+2)+\log (b+2))$ bookkeeping, and the configuration counter uses $O(b+\log (n+2))$ bits. Since $\log (n+2)=O(f(n))=O(g(n))$ eventually, $D$ is total and belongs to $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g)$. The cap is a computable number derived only from the fixed constructor for $g$, so no varying program-dependent constant has to be estimated.

Suppose $D\in \mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f)$, decided by a fixed read-only-input machine $M$ using at most $Cf(n)$ cells for all sufficiently long inputs. Choose any padded code for $M$ from the effective enumeration. For this fixed $M$, the published simulator's encoded-storage cost is $O_M(f(n)+\log (n+2))=o(g(n))$. Hence a sufficiently long padded self-code $z$ lets the simulation of $M(z)$ fit below $b=\lfloor g(n)\mathrm{/}4\rfloor$; the configuration clock does not interrupt a halting computation. On that input $D(z)$ returns the opposite of $M(z)$, a contradiction. Finally $f=o(g)$ gives the ordinary inclusion $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f)\subseteq \mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(g)$, so the inclusion is strict.

Regard its endmarked input tape as an ordinary tape. By the local-model definition the input head is confined to its $n+2$ input positions, and the machine visits $O(s(n))$ work cells.

Therefore the total visited-cell count is $O(n+s(n))$, which is the claimed all-tapes DSPACE bound.

Both bounds meet the local work-space-constructibility contract. On unary input $1^n$, count its length in binary, using $O(\log (n+2))$ cells, and add $2$. The binary length and a power-of-two test compute $f(n)=\lceil {\log }_2(n+2)\rceil$ in the same space; outputting the binary count gives $g(n)=n$ within $O(n)$ cells. Also $f(n)\ge \lceil {\log }_2(n+2)\rceil$ tautologically, $f(n)=o(n)$, and $g(n)$ satisfies the hierarchy's address lower bound for all sufficiently large $n$. Thus The read-only-workspace space hierarchy theorem applies and yields a language in $\mathrm{D}\mathrm{W}\mathrm{O}\mathrm{R}\mathrm{K}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n)\setminus L$.

The bridge Read-only work space becomes all-tapes space after charging input puts that witness language in $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n+n)=\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(2n)$, hence in PSPACE. For any $L$ computation, the same bridge gives $\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(n+f(n))\subseteq \mathrm{D}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(2n+O(1))\subseteq \mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, by the polynomial-space definition. The witness lies outside $L$ by step 1.1, so the inclusion is proper.

For the forward implication, validate $y$ and reject it if malformed. Otherwise recover $x$ and run the supplied $A$ decider. By the padding definition its answer is correct, and its cost is $O((N+1{)}^c+t(\mathrm{\mid }x\mathrm{\mid }))$. Since $p(n)>n$, the set of lengths $n$ with $p(n)=N$ is finite; maximizing gives the displayed worst-case bound, including lengths with no valid pad.

For the converse, on $x$ of length $n$ construct $x\mathrm{\#}{1}^{p(n)-n-1}$ and run the independently supplied padded-language decider. The exponent is nonnegative, including at $n=0$, and this valid pad belongs to the padded language exactly when $x\in A$. Construction costs $O(p(n{)}^c)$ and the decider costs $O(u(p(n)))$, giving the claimed sum.

The Gap Theorem for abstract measures (Hartmanis--Hopcroft, Theorem 7) applies to the given Blum measure and recursive $r>\mathrm{i}\mathrm{d}$. Its finite-stage construction uses only bounded tests of the decidable Blum predicate ${\mathrm{\Phi }}_i(x)=m$; it does not attempt to decide whether a program is eventually below a bound. The resulting recursive nondecreasing $t$ has the stage invariant that every indexed program eventually below $r\circ t$ is also eventually below $t$. Hence ${\mathcal{C}}_t={\mathcal{C}}_{r\circ t}$.

The Union Theorem for abstract measures (Hartmanis--Hopcroft, Theorem 16) applies to the effective strictly increasing sequence $(f_i)$. Its recursive finite-injury construction produces a recursive $t$ with two complementary invariants: every $f_i$ is eventually at most $t$, and each indexed program that is outside every ${\mathcal{C}}_{f_i}$ exceeds $t$ infinitely often. These give respectively ${\bigcup }_i{\mathcal{C}}_{f_i}\subseteq {\mathcal{C}}_t$ and the reverse inclusion.

Each hierarchy compares two deterministic classes or two nondeterministic classes at separated resource bounds, such as $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(f)$ versus $\mathrm{D}\mathrm{T}\mathrm{I}\mathrm{M}\mathrm{E}(g)$.

By [L1] and the definition of $P$, the $P$ versus $NP$ question compares the unions of deterministic and nondeterministic polynomial-time classes. A separation needs one language in $NP$ outside every deterministic polynomial-time class; equality needs polynomial deterministic simulations for all $NP$ languages. The witnesses in step 1.1 only separate two bounds in the same model, and their bounds and witnesses may vary. These stated conclusions do not themselves provide either of the required cross-model arguments. This is a comparison of what the theorem statements assert, not a formal independence claim about their consequences in an axiomatic theory.

Fix a machine $M$ that halts after one transition without reading its input, and consider the valid pairs $⟨M,x⟩$ as $\mathrm{\mid }x\mathrm{\mid }$ grows. The simulated computation respects the bound $f=1$, but [F1] requires the specified simulator to read the complete pair before simulation. Reading that unbounded input takes at least linear time in its length.

Hence this unrestricted diagonalizer is not an $O(1)$-time computation, despite every selected run of $M$ taking one step. A candidate's resource bound alone therefore does not bound decoding and universal-simulation overhead; a separate clock and a proved gap are needed.