The read-only-workspace space hierarchy theorem

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.