<p>From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: &quot;the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (encodings over (0,1)) of such machines provides an indexing of ...we have Theorem: No universal simulator for this indexing can run in .&quot;</p>
<p>He then goes on to say: &quot;can it be proved that  for any indexing of  requires more than  to compute? We have proved this for a wide class of indexings, namely counter indexings satisfying the succinct composition property.&quot;</p>
<ul>
<li><p> is the graph of the universal function  and represents the minimum power necessary to simulate  uniformly.</p>
</li>
<li><p>The counter indexing (or polynomial time counters) he is referring to is talked about in the answer here: <a href="https://cs.stackexchange.com/questions/126615/how-does-an-enumerator-for-machines-for-languages-work/126621?noredirect=1#comment266467_126621">https://cs.stackexchange.com/questions/126615/how-does-an-enumerator-for-machines-for-languages-work/126621?noredirect=1#comment266467_126621</a></p>
</li>
</ul>
<p>I'm wondering what causes simulation of the enumerated machines to be difficult, and can it be circumvented--namely: does there exist an enumeration of machines for all languages in <span class="math-container">$$</span> that describes the machines in such a way that allows the machines, as specified, to be simulated efficiently by a simulator (with no more than  overhead) on any input--or (basically) as Kozen puts it &quot;allow(s) easy construction of programs from (their) specification&quot;?</p>
<p>Looking for any progress that has been made since Kozen asked ^ the above question ^.</p>

CC BY-SA 4.0
2020-06-24T06:48:57.547Z
I don’t quite understand what you are asking. The most obvious simulator of the usual enumeration *has* the property that it simulates any *fixed* polytime Turing machine $M$ with only a polynomial-time overhead (which however depends on $M$). On the other hand, for *any* enumeration, it is impossible for a simulator as such to run in polytime, as this would contradict the time hierarchy theorem. And, indeed, it is likely impossible for any such simulator to run in PSPACE, as this would imply that there is $c$ such that $\mathrm P\subseteq\mathrm{DSPACE}(n^c)$, which is assumed to be false.
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T13:11:59.540Z
Im probably misunderstanding something. Kozen says in his paper that for the usual enumeration (the polynomial time counter indexing of P) _no_ universal simulator for this indexing can run in . He then goes on to say a wide class of indexings of  require more than  to compute. I know there is the efficient simulation theorem that for any TM there is only log overhead to simulate it on some other TM... what I'm not understanding is what the efficient simulation result, what you are talking about and what Kozen is talking about all concede.
mark
CC BY-SA 4.0
2020-06-24T13:35:19.853Z
I took "No universal simulator for this indexing can run in " to mean the overhead on running some poly machine on some input must be more than , as each machine. They all run in P time by definition, so something _else_ (such as overhead) has to be causing the slowdown? Just a bit confused why we can't simulate all these machines efficiently? Maybe it has to do with the fact that we are required to simulate a whole class of TMs and the efficient simulation theorem only applies to simulating a single TM on another? Or maybe overhead idea is the wrong interpretation.
mark
CC BY-SA 4.0
2020-06-24T13:50:58.080Z
You seem to be confused by basic terminology. The reason that the simulator does not run in P, or even in PSPACE, has nothing to do with “inefficiency” of the simulation. I don’t know how exactly Kozen defines “Turing machines with polynomial time counters”, but basically, it amounts to the following: the input of the simulator is a triple $(M,k,x)$, where $M$ is a description of the simulated Turing machine, $k$ is a time-bound exponent, and $x$ is the simulated input. The simulator runs $M$ on input $x$ for at most $|x|^k$ steps, and outputs either the output of the simulated TM, or, ...
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T13:54:06.190Z
... say, NO, if the time bound is exhausted. This simulation needs time $|x|^k$ times some small overhead, and may likewise use space $|x|^k$ times some small overhead. For simulation of any specific TM, $M$ and $k$ are constants, hence this is polynomial time, and the time and space used is really the time and space needed by $M$ with a small overhead. However, in terms of the input of the simulator, the bound is *exponential*, as $|x|^k$ is exponential in $k$. Thus, the simulator runs in exponential time and space.
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T13:59:31.263Z
In order for a simulator to run in PSPACE, you would need to be able, given $(M,k,x)$, to simulate machine $M$ on input $x$ for $|x|^k$ steps using space only $(|M|+|x|+k)^c$ for some universal constant $c$.
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T13:59:40.597Z
Ahh.thank you for clearing up why a simulator for that particular enumeration is not in P.  Was confused. This motivates the original question. Are there any universal simulators for the class P that are in P itself? Are there any whose results can at least be verified in poly time?
mark
CC BY-SA 4.0
2020-06-24T14:01:21.013Z
No, because it contradicts the time hierarchy theorem, I already told you. If the simulator runs in time $n^c$, it cannot simulate languages in $\mathrm{DTIME}(n^{c+1})\smallsetminus\mathrm{DTIME}(n^c)$.
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T14:03:10.987Z
oh, Gotchya, thanks! how about in NP or results of simulator at least verifibale in poly time? what is the fastest the simulator can go?
mark
CC BY-SA 4.0
2020-06-24T14:06:11.943Z
Whether $\mathrm{P\subseteq NTIME}(n^c)$ for some constant $c$ is an open problem, but as far as I am aware, the expected answer is the same, namely $\mathrm{DTIME}(n^{c+1})\nsubseteq\mathrm{NTIME}(n^c)$.
Emil Jeřábek
CC BY-SA 4.0
2020-06-24T14:11:43.550Z
Oh, and by padding the representation suitably, you can make a universal simulator run in time as close to polynomial as you want. For example, let $A$ be the Ackermann function, and $\alpha$ its inverse. If you represent a machine $M$ with a time-bound exponent $k$ by $(M,A(k))$ instead of $(M,k)$, the simulator will run in time $n^{O(\alpha(n))}$ or so.
Emil Jeřábek
<cc.complexity-theory><polynomial-time><enumeration>
Are there enumerations of machines for all languages in  such that there exists a simulator that can efficiently run all the machines enumerated?
mark
# Are there enumerations of machines for all languages in  such that there exists a simulator that can efficiently run all the machines enumerated?

(Asked by: username_0 on 2020-06-23)

From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: "the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (encodings over (0,1)) of such machines provides an indexing of ...we have Theorem: No universal simulator for this indexing can run in ."

He then goes on to say: "can it be proved that for any indexing of requires more than to compute? We have proved this for a wide class of indexings, namely counter indexings satisfying the succinct composition property."

* is the graph of the universal function and represents the minimum power necessary to simulate uniformly.
* The counter indexing (or polynomial time counters) he is referring to is talked about in the answer here: <https://cs.stackexchange.com/questions/126615/how-does-an-enumerator-for-machines-for-languages-work/126621?noredirect=1#comment266467_126621>

I'm wondering what causes simulation of the enumerated machines to be difficult, and can it be circumvented--namely: does there exist an enumeration of machines for all languages in $$ that describes the machines in such a way that allows the machines, as specified, to be simulated efficiently by a simulator (with no more than overhead) on any input--or (basically) as Kozen puts it "allow(s) easy construction of programs from (their) specification"?

Looking for any progress that has been made since Kozen asked ^ the above question ^.

**Tags:** cc.complexity-theory, polynomial-time, enumeration
> **Comments:**
> **username_1**: I don’t quite understand what you are asking. The most obvious simulator of the usual enumeration *has* the property that it simulates any *fixed* polytime Turing machine $M$ with only a polynomial-time overhead (which however depends on $M$). On the other hand, for *any* enumeration, it is impossible for a simulator as such to run in polytime, as this would contradict the time hierarchy theorem. And, indeed, it is likely impossible for any such simulator to run in PSPACE, as this would imply that there is $c$ such that $\mathrm P\subseteq\mathrm{DSPACE}(n^c)$, which is assumed to be false.  
> **username_0**: Im probably misunderstanding something. Kozen says in his paper that for the usual enumeration (the polynomial time counter indexing of P) _no_ universal simulator for this indexing can run in . He then goes on to say a wide class of indexings of  require more than  to compute. I know there is the efficient simulation theorem that for any TM there is only log overhead to simulate it on some other TM... what I'm not understanding is what the efficient simulation result, what you are talking about and what Kozen is talking about all concede.  
> **username_0**: I took "No universal simulator for this indexing can run in " to mean the overhead on running some poly machine on some input must be more than , as each machine. They all run in P time by definition, so something _else_ (such as overhead) has to be causing the slowdown? Just a bit confused why we can't simulate all these machines efficiently? Maybe it has to do with the fact that we are required to simulate a whole class of TMs and the efficient simulation theorem only applies to simulating a single TM on another? Or maybe overhead idea is the wrong interpretation.  
> **username_1**: You seem to be confused by basic terminology. The reason that the simulator does not run in P, or even in PSPACE, has nothing to do with “inefficiency” of the simulation. I don’t know how exactly Kozen defines “Turing machines with polynomial time counters”, but basically, it amounts to the following: the input of the simulator is a triple $(M,k,x)$, where $M$ is a description of the simulated Turing machine, $k$ is a time-bound exponent, and $x$ is the simulated input. The simulator runs $M$ on input $x$ for at most $|x|^k$ steps, and outputs either the output of the simulated TM, or, ...  
> **username_1**: ... say, NO, if the time bound is exhausted. This simulation needs time $|x|^k$ times some small overhead, and may likewise use space $|x|^k$ times some small overhead. For simulation of any specific TM, $M$ and $k$ are constants, hence this is polynomial time, and the time and space used is really the time and space needed by $M$ with a small overhead. However, in terms of the input of the simulator, the bound is *exponential*, as $|x|^k$ is exponential in $k$. Thus, the simulator runs in exponential time and space.  
> **username_1**: In order for a simulator to run in PSPACE, you would need to be able, given $(M,k,x)$, to simulate machine $M$ on input $x$ for $|x|^k$ steps using space only $(|M|+|x|+k)^c$ for some universal constant $c$.  
> **username_0**: Ahh.thank you for clearing up why a simulator for that particular enumeration is not in P.  Was confused. This motivates the original question. Are there any universal simulators for the class P that are in P itself? Are there any whose results can at least be verified in poly time?  
> **username_1**: No, because it contradicts the time hierarchy theorem, I already told you. If the simulator runs in time $n^c$, it cannot simulate languages in $\mathrm{DTIME}(n^{c+1})\smallsetminus\mathrm{DTIME}(n^c)$.  
> **username_0**: oh, Gotchya, thanks! how about in NP or results of simulator at least verifibale in poly time? what is the fastest the simulator can go?  
> **username_1**: Whether $\mathrm{P\subseteq NTIME}(n^c)$ for some constant $c$ is an open problem, but as far as I am aware, the expected answer is the same, namely $\mathrm{DTIME}(n^{c+1})\nsubseteq\mathrm{NTIME}(n^c)$.  
> **username_1**: Oh, and by padding the representation suitably, you can make a universal simulator run in time as close to polynomial as you want. For example, let $A$ be the Ackermann function, and $\alpha$ its inverse. If you represent a machine $M$ with a time-bound exponent $k$ by $(M,A(k))$ instead of $(M,k)$, the simulator will run in time $n^{O(\alpha(n))}$ or so.  

---

## 0 answers

