[FOM] Polynomial Turing machines

[Mitchell Spector]

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