# Space requirement of a universal Turing machine

Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$.

If $B$ is restricted to using at most $n$ memory cells of its tape and the memory cells of $A$ and $B$ can assume the same number of states, how much space does $A$ require at least to simulate any $B$?

$A$ knows the $n$ of the $B$ of the $g$ its given.

I'm not interested in how this behaves for small $n$ or constant additive terms but would like to know constant multiplicative factors. So if $A$'s space requirement is $3 \cdot n^2 + |g|$ memory cells, that'd be nice to know, not just that its space complexity is $\in \mathcal{O}(n^2 + |g|)$.

The constant depends on the size of the respective tape alphabets. If the two are the same and you're very careful, you can probably make do with only $n + O(1)$ space, where the constant only depends on the simulated machine. The idea is to store the tape of the simulated machine from the point of view of the cell pointed to by the head, interleaving both sides of the tape. This is not the most time-efficient simulation, but the blow-up in time is still only polynomial.
• Is this also possible if $A$ does something other than simulating $B$, too (without doing one of them first)? Like incrementing a counter after each step of $B$ so $A$ can figure out how many steps it took $B$ to halt (and to abort simulation of $B$ if it doesn't ($B$ has a limited number of states because it can only address $n$ memory cells)). Another $n$ memory cells would be required for the counter, of course. So is it possible to do this with $2 \cdot n + \mathcal{O}(1)$ memory cells? – UTF-8 Jun 6 '17 at 20:01
• That's the exact thing I'm concerned/confused about. You can't have this in the finite automaton because $n$ can be arbitrarily big. With 2 tapes, the solution is obvious. But how would you solve it with only 1 tape? – UTF-8 Jun 6 '17 at 22:28