1
$\begingroup$

Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps.

Wikipedia's page on EXPTIME-complete says it takes O(k) time but the page on universal Turing machines says O(k log k) on a multitape machine which only implies a single tape machine might do even worse.

Am I mixing things up? What is the best known bound for the given problem? Is it provably optimal? If not, what is the best bound that probably cannot be beaten?

Thanks for clearing this long standing doubt

$\endgroup$
11
  • $\begingroup$ I don’t see where the $\log k$ comes from, but there definitely has to be some dependence on $|M|$. $\endgroup$ Apr 29, 2019 at 17:56
  • 1
    $\begingroup$ Why does a single tape have to be worse? You're simulating something simpler, so it should be easier. $\endgroup$ Apr 29, 2019 at 18:15
  • 1
    $\begingroup$ So the difference is that the first is talking about a single-tape Turing machine simulating a single-tape Turing machine, and the second about a multi-tape Turing machine simulating a multi-tape Turing machine. The $\log n$ factor comes from the case where the simulated machine has more tapes than the simulating machine. $\endgroup$ Apr 30, 2019 at 10:49
  • 1
    $\begingroup$ Has it been proven optimal? See the time-hierarchy theorem. $\endgroup$ Apr 30, 2019 at 10:54
  • 1
    $\begingroup$ Um ... it proves it optimal up to a $\log$ factor in almost all realistic cases (time-constructible running times). $\endgroup$ Apr 30, 2019 at 10:57

1 Answer 1

1
$\begingroup$

This problem has given me a headache too so I'll post for future reference. The way I understand it the two wikipedia articles you're referencing aren't about the same problem.

Problem number one is : given $<M,k>$ where $M$ describes a machine and $k$ an integer written in base two how long does it take to simulate machine $M$ for exactly $k$ steps ?

Problem number two is : given $<M>$ where $M$ describes a machine, how long does it take to simulate $M$ ? You will express your result using $k_M$ the number of steps $M$ takes to stop. (I formulate this question that way to expressly show the difference with the previous one)

The article about EXP time is about the first problem.

The article about UTMs is about the second problem.

As for the second problem :

I know for sure the solution : if the machines $M$ can have an arbitrary number of tapes then the best known simulation will run for $O(k_M*log(k_M))$ steps. (The big-$O$ hides constant depending on the size of $M$. I believe this constant grows linearly in the size of $M$. I'm just talking about the size of $M$, the dependance relative to the number of tapes could make this constant worse. On a side note I believe if we worked with Turing machines working with 2-dimensionnal tapes these constant would grow in the square root of the size of $M$, which is interesting to me.)

I believe that, if the machines $M$ number of tapes are bounded by a constant $m$ then there is a $m+2$ tape TM which simulate $M$ for any such $M$ in time $O(k_M)$. The idea is that on one additionnal tape you store the table transition of $M$ and on another one you store the current state of the heads. (I only thought about it so I may be wrong). I do not know if you can do better than $m+2$ tapes. In particular, maybe we could get a universal constant ?

As for the first problem :

The first problem is stricly more difficult than the second one, so definitely $O(k log(k))$ (call an oracle for the second problem on $<M,1>$, $<M,2>$, ... $<M,2^i>$ ... $<M,2^{log(k_M)}>$) . I do believe the wikipedia article is referencing this problem, so, for me, the article is wrong.

However, if you know the number of tapes you are working with it - or even better the machine you are working with - it becomes $O(k)$, but it's not immediately trivial because of a technicality. First let's be formal.

Let $m$ be a number of tapes. Call $C_m$ the following problem : "Given $<M,k>$ a machine with $m$ tapes and an integer written in base 2, simulate machine $M$ for $k$ steps " How long to solve $C_m$ ? (I haven't made "simulate machine $M$ for $k$ steps" mean something formal, in particular it's not exactly time equivalent for all we know to "write the output of $M$ after $k$ steps", but let's just gloss over that detail and work with an intuitive definition of what "simulating" means.)

I have a $m+3$ machine which does it in $O(k)$ steps. On $m+2$ tapes you do the simulation of $M$ as described for problem number 2. On the extra tape you write $k$ in unary at the beginning of the computation with symbol $|$, then when you simulate $M$, for each simulation step you take off one $|$, when you reach the blank symbol on your counting tape you stop.

If you had tried to be clever and used a binary counter you would have added a log factor to this computation, because each time you'd tried to increment the counter by one you may have had to change/scroll over log(k) bits. (Well maybe it's not exactly a log factor but you get the idea).

This simulation does add a big space overhead. I have a simulation which only uses $\sqrt k$ bits for the counter but no better yet.

There must be a place where this has all been made formal and we get constant factor overhead for both space and time, but I do not know of it, it's usually the kind of details omitted in textbooks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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