<p>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.</p>
<p>Problem number one is : given <span class="math-container">$&lt;M,k&gt;$</span> where <span class="math-container">$M$</span> describes a machine and <span class="math-container">$k$</span> an integer written in base two how long does it take to simulate machine <span class="math-container">$M$</span> for exactly <span class="math-container">$k$</span> steps ?</p>
<p>Problem number two is : given <span class="math-container">$&lt;M&gt;$</span> where <span class="math-container">$M$</span> describes a machine, how long does it take to simulate <span class="math-container">$M$</span> ? You will express your result using <span class="math-container">$k_M$</span> the number of steps <span class="math-container">$M$</span> takes to stop. (I formulate this question that way to expressly show the difference with the previous one)</p>
<p>The article about EXP time is about the first problem.</p>
<p>The article about UTMs is about the second problem.</p>
<p><strong>As for the second problem :</strong></p>
<p>I know for sure the solution : if the machines <span class="math-container">$M$</span> can have an arbitrary number of tapes then the best known simulation will run for <span class="math-container">$O(k_M*log(k_M))$</span> steps. (The big-<span class="math-container">$O$</span> hides constant depending on the size of <span class="math-container">$M$</span>. I believe this constant grows linearly in the size of <span class="math-container">$M$</span>. I'm just talking about the size of <span class="math-container">$M$</span>, 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 <span class="math-container">$M$</span>, which is interesting to me.)</p>
<p>I believe that, if the machines <span class="math-container">$M$</span> number of tapes are bounded by a constant <span class="math-container">$m$</span> then there is a <span class="math-container">$m+2$</span> tape TM which simulate <span class="math-container">$M$</span> for any such <span class="math-container">$M$</span> in time <span class="math-container">$O(k_M)$</span>. The idea is that on one additionnal tape you store the table transition of <span class="math-container">$M$</span> 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 <span class="math-container">$m+2$</span> tapes. In particular,  maybe we could get a universal constant ?</p>
<p><strong>As for the first problem :</strong></p>
<p>The first problem is stricly more difficult than the second one, so definitely <span class="math-container">$O(k log(k))$</span> (call an oracle for the second problem on <span class="math-container">$&lt;M,1&gt;$</span>, <span class="math-container">$&lt;M,2&gt;$</span>, ... <span class="math-container">$&lt;M,2^i&gt;$</span> ... <span class="math-container">$&lt;M,2^{log(k_M)}&gt;$</span>) . I do believe the wikipedia article is referencing this problem, so, for me, the article is wrong.</p>
<p><strong>However</strong>, if you know the number of tapes you are working with it - or even better the machine you are working with - it becomes <span class="math-container">$O(k)$</span>, but it's not immediately trivial because of a technicality. First let's be formal.</p>
<p>Let <span class="math-container">$m$</span> be a number of tapes. Call <span class="math-container">$C_m$</span> the following problem : &quot;Given <span class="math-container">$&lt;M,k&gt;$</span> a machine with <span class="math-container">$m$</span> tapes and an integer written in base 2, simulate machine <span class="math-container">$M$</span> for <span class="math-container">$k$</span> steps &quot; How long to solve <span class="math-container">$C_m$</span> ? (I haven't made &quot;simulate machine <span class="math-container">$M$</span> for <span class="math-container">$k$</span> steps&quot; mean something formal, in particular it's not exactly time equivalent for all we know to &quot;write the output of <span class="math-container">$M$</span> after <span class="math-container">$k$</span> steps&quot;, but let's just gloss over that detail and work with an intuitive definition of what &quot;simulating&quot; means.)</p>
<p>I have a <span class="math-container">$m+3$</span> machine which does it in <span class="math-container">$O(k)$</span> steps. On <span class="math-container">$m+2$</span> tapes you do the simulation of <span class="math-container">$M$</span> as described for problem number 2. On the extra tape you write <span class="math-container">$k$</span> in <strong>unary</strong> at the beginning of the computation with symbol <span class="math-container">$|$</span>, then when you simulate <span class="math-container">$M$</span>, for each simulation step you take off one <span class="math-container">$|$</span>, when you reach the blank symbol on your counting tape you stop.</p>
<p>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).</p>
<p>This simulation does add a big space overhead. I have a simulation which only uses <span class="math-container">$\sqrt k$</span> bits for the counter but no better yet.</p>
<p>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.</p>

CC BY-SA 4.0
2022-02-16T13:48:34.770Z
2022-02-16T13:48:34.770Z
ULechine
<p>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.</p>

<p>Wikipedia's page on <a href="https://en.wikipedia.org/wiki/EXPTIME" rel="nofollow noreferrer">EXPTIME-complete</a> says it takes O(k) time but the page on <a href="https://en.wikipedia.org/wiki/Universal_Turing_machine#Efficiency" rel="nofollow noreferrer">universal Turing machines</a> says O(k log k) on a multitape machine which only implies a single tape machine might do even worse. </p>

<p>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?</p>

<p>Thanks for clearing this long standing doubt</p>

CC BY-SA 4.0
2019-04-29T17:56:10.690Z
I don’t see where the $\log k$ comes from, but there definitely has to be some dependence on $|M|$.
Emil Jeřábek
CC BY-SA 4.0
2019-04-29T18:15:52.183Z
Why does a single tape have to be worse? You're simulating something simpler, so it should be easier.
Peter Shor 
CC BY-SA 4.0
2019-04-30T03:44:52.443Z
@EmilJe The Wikipedia page says O(k log k steps), I too don't know why.
ghosts_in_the_code
CC BY-SA 4.0
2019-04-30T03:45:56.120Z
@PeterShor I think they're talking about the machine doing the simulation rather than the machine being simulated. They've not given details about the machine being simulated so I assumed it's a single tape machine (I could be wrong).
ghosts_in_the_code
CC BY-SA 4.0
2019-04-30T10:39:45.200Z
@ghosts_in_the_code: From the abstract of Hennie and Stearn's paper, cited in your second Wikipedia article:: *The purpose of this paper is to show that, if a given function requires computation time T
for a k-tape realization, then it requires at most computation time T log T for a two-tape
realization.*
Peter Shor 
CC BY-SA 4.0
2019-04-30T10:49:09.623Z
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.
Peter Shor 
CC BY-SA 4.0
2019-04-30T10:51:16.157Z
@PeterShow Okay thanks a lot. So for a single tape machine simulating a single tape machine, O(k) is the best known solution but it's not proven optimal?
ghosts_in_the_code
CC BY-SA 4.0
2019-04-30T10:54:26.870Z
Has it been proven optimal? See the [time-hierarchy theorem](https://en.wikipedia.org/wiki/Time_hierarchy_theorem).
Peter Shor 
CC BY-SA 4.0
2019-04-30T10:55:37.937Z
@PeterShor Um, I have seen it actually. That just proves the existence of harder problems, right?
ghosts_in_the_code
CC BY-SA 4.0
2019-04-30T10:57:10.887Z
Um ... it proves it optimal up to a $\log$ factor in almost all realistic cases (time-constructible running times).
Peter Shor 
CC BY-SA 4.0
2019-04-30T10:58:04.750Z
@PeterShor Oh okay, thanks.
ghosts_in_the_code
<turing-machines><exp-time-algorithms><universal-turing-machines><worst-case>
Asymptotic time required to simulate a Turing machine M for k steps
ghosts_in_the_code
# Asymptotic time required to simulate a Turing machine M for k steps

(Asked by: username_0 on 2019-04-29)

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](https://en.wikipedia.org/wiki/EXPTIME) says it takes O(k) time but the page on [universal Turing machines](https://en.wikipedia.org/wiki/Universal_Turing_machine#Efficiency) 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

**Tags:** turing-machines, exp-time-algorithms, universal-turing-machines, worst-case
> **Comments:**
> **username_1**: I don’t see where the $\log k$ comes from, but there definitely has to be some dependence on $|M|$.  
> **username_2**: Why does a single tape have to be worse? You're simulating something simpler, so it should be easier.  
> **username_0**: @EmilJe The Wikipedia page says O(k log k steps), I too don't know why.  
> **username_0**: @PeterShor I think they're talking about the machine doing the simulation rather than the machine being simulated. They've not given details about the machine being simulated so I assumed it's a single tape machine (I could be wrong).  
> **username_2**: @ghosts_in_the_code: From the abstract of Hennie and Stearn's paper, cited in your second Wikipedia article:: *The purpose of this paper is to show that, if a given function requires computation time T for a k-tape realization, then it requires at most computation time T log T for a two-tape realization.*  
> **username_2**: 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.  
> **username_0**: @PeterShow Okay thanks a lot. So for a single tape machine simulating a single tape machine, O(k) is the best known solution but it's not proven optimal?  
> **username_2**: Has it been proven optimal? See the [time-hierarchy theorem](https://en.wikipedia.org/wiki/Time_hierarchy_theorem).  
> **username_0**: @PeterShor Um, I have seen it actually. That just proves the existence of harder problems, right?  
> **username_2**: Um ... it proves it optimal up to a $\log$ factor in almost all realistic cases (time-constructible running times).  
> **username_0**: @PeterShor Oh okay, thanks.  

---

## 1 answers

### Answer by username_3 on 2022-02-16. Score: 1

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


---

