Space-bounded universal simulation

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.