[FOM] Polynomial Turing machines

[Mitchell Spector]

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:

For two-tape Turing machines and k >= 1, the degree is 0''.  The same holds for Turing machines with 
more than two tapes.

For one-tape Turing machines and k >= 2, the same method shows that the degree is again 0''.

I don't know the answer for smaller values of k.


(The degree is also 0'' if we look instead at Turing machines that run in polynomial time, instead 
of Turing machines that run in time O(n^k) for some fixed k.)


In fact, these sets of degree 0'' are all Sigma_2 in the arithmetical hierarchy, and they are 
recursively isomorphic to {e | phi_e is not total}.


Here's an outline.  The two-tape version is a bit simpler, so that's where I'll start.



TWO-TAPE TURING MACHINES

Fix k >= 1.

Pick a standard enumeration phi_0, phi_1, ..., of all partial recursive functions.


Consider the set of two-tape Turing machines which run in time O(n^k) for input strings of size n. 
We'll show that this set is recursively isomorphic to {e | phi_e is not total}; the latter is a set 
of Turing degree 0''.

A Tarski-Kuratowski computation shows that the set of Turing machines which run in time O(n^k) is 
Sigma_2 in the arithmetical hierarchy:

Turing machine T runs in time O(n^k) iff
(there exists C)(there exists N)(for all n)(n > N implies "T applied to input n halts in at most 
C(log n)^k steps").

It follows that the set of such Turing machines is 1-reducible to {e | phi_e is not total}, since 
the latter is a standard Sigma_2 set which is complete for one-one reducibility.



Next we'll show that {e | phi_e is not total} is 1-reducible to the set of such Turing machines:

For any index e, consider the following algorithm, which we'll implement using a two-tape Turing 
machine T_e:

Stage 1. Given an input string, let n be the length of the string.  Compute exactly n Turing-machine 
steps in the successive computations phi_e(0), phi_e(1), ....  What is meant by this is: first 
compute phi_e(0); if that computation halts, compute phi_e(1); if that computation halts, compute 
phi_e(2); etc. -- but only execute n machine steps total in all these successive computations 
combined (including the counting calculation that computes the successive arguments 0, 1, 2, ...). 
(If phi_e is not a total function, then we'll never get past some particular phi_e(x) calculation, 
no matter how long the input string is.)

Stage 2. If the very last thing done at the end of the n-th step above is the completion of some 
calculation phi_e(x), then use an idle loop to do nothing for another 2^n steps.

Stage 3. Halt.  (We don't care what the output is.)

Constructing a 2-tape Turing machine to carry out this algorithm is straightforward.  Here are a few 
details for Stage 1.  The input string is presented on tape 1.  Tape 2 is used to carry out the 
(first n steps of the) computation of phi_e(0), phi_e(1), ... via a suitably modified version of a 
1-tape Turing-machine implementation that computes phi_e(0), phi_e(1), ....  The Turing machine for 
the computation needs to be modified so that, at the end of each step in a phi_e(x) computation, a 
non-blank symbol in the input string on tape 1 is changed to some otherwise unused symbol.  When the 
last non-blank input symbol is changed, we're done with Stage 1.  As for Stage 2, the test there is 
done by checking whether the last Turing-machine state from a phi_e(x) computation was a final state 
(in the original machine for phi_e); if it was a former final state, transition to a new state for 
the purpose of whiling away the time for 2^n additional steps.


The key properties of the Turing machines T_e are:

Property 1:  If phi_e is total, then T_e does not run in polynomial time.  (For infinitely many n, 
any input string of size n satisfies the condition in Stage 2.  So, for those infinitely many n, T_e 
requires at least 2^n steps on any input of size n.)

Property 2: If phi_e is not total, then T_e runs in time O(n).  (For all sufficiently large n, any 
input string of size n fails to satisfy the condition in Stage 2.  Everything else can be done in 
time O(n); in addition to some constant overhead, the machine just simulates n steps in the 
successive computations phi_e(0), phi_e(1), ..., taking at most some constant amount of time for 
each simulated step.)


Since the function mapping e to T_e is 1-1, it follows that, for any k >= 1, {e | phi_e is not 
total} is 1-reducible to {T | T is a two-tape Turing machine that runs in time O(n^k)}.

This completes the proof that those sets are recursively isomorphic.  The set {T | T is a two-tape 
Turing machine that runs in polynomial time} is also recursively isomorphic to the other sets.



ONE-TAPE TURING MACHINES

We can implement the same algorithm as above, but on a one-tape Turing machine, by just storing both 
the input string and the computations of phi_e(0), phi_e(1), ... on the same tape, separated by some 
delimiter character.

Everything works the same way as before, except that Property 2 needs to be modified:

Property 2 for one-tape Turing machines: If phi_e is not total, then T_e runs in time O(n^2).  (In 
addition to the number of steps counted in the two-tape version, we need to count the steps needed 
to move the tape head back and forth between the data that used to be on tape 1 and the data that 
used to be on tape 2.  For each step in the phi_e(x) computation, we need to run the tape head to 
the input string to mark one symbol, and then move it back to the phi_e(x) computation.  That adds 
O(n) more steps for each of the n steps in the phi_e(x) computations, so the total now comes to O(n^2).

So, following essentially the same argument as above, we find that the set {e | phi_e is not total}, 
the set {T | T is a one-tape Turing machine that runs in polynomial time}, and all the sets {T | T 
is a one-tape Turing machine that runs in O(n^k)}, for k >= 2, are recursively isomorphic.

----------


I would imagine that this is likely already known.  I'd appreciate hearing of any reference.


--
Mitchell Spector
E-mail: spector at alum.mit.edu