2
$\begingroup$

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|)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – UTF-8 Jun 6 '17 at 20:01
  • $\begingroup$ Yes, I see no reason why not, especially if you allow using several tapes. In general it may depend on the exact model. The slight problem is that you need to know where the counter terminates and where the simulated tape starts. $\endgroup$ – Yuval Filmus Jun 6 '17 at 20:01
  • $\begingroup$ 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? $\endgroup$ – UTF-8 Jun 6 '17 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.