[FOM] Polynomial Turing machines
Mitchell Spector
spector at alum.mit.edu
Fri Dec 30 15:16:54 EST 2011
leivant wrote:
> On 12/29/11 12:29 p, Mitchell Spector wrote:
>> rpax0 at seznam.cz wrote:
>>> Does someone know:
>>> what is the complexity (in the arithmetical hierarchy) of Godel numbers of Turing machines
>>> that run in time O(n^k) for a fixed k>0?
>>> Thank you, Jan Pax
>>
>> The following is a partial solution to Jan's question, if I'm not mistaken in some part of the proof:
>>
>> [Proof excised for brevity]
>> ----------
>> I would imagine that this is likely already known. I'd appreciate hearing of any reference.
>
> For PTime (without the fixed degree) see:
>
> Petr Hajek:
> Arithmetical Hierarchy and Complexity of Computation.
> TCS 1979, pages 227-237.
> Theorem 2, page 230.
>
> A variant of that proof would work for fixed exponent as well.
>
> best wishes - daniel
Thanks for the reference, Daniel. It looks like I rediscovered essentially the same method as Hajek.
In fact, Hajek does mention the fixed-exponent case briefly, at least for multi-tape Turing
machines, immediately after the proof of the theorem you cited:
"Remark. The set {i : M_i works in linear time} is obviously also Sigma^0_2; the above proof shows
that this set is Sigma^0_2-complete. Similarly for quadratic time etc." (Bottom of p. 230.)
A fast look at the paper indicates that Hajek would only able to handle the same values of the
exponent as in my outline (although he doesn't spell it out explicitly for single-tape machines).
Thank you for taking the time to look up and post the citation.
Best wishes,
Mitchell
More information about the FOM
mailing list