[FOM] Polynomial Turing machines

pax0 at seznam.cz pax0 at seznam.cz
Sat Dec 24 14:21:05 EST 2011

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

More information about the FOM mailing list