3
$\begingroup$

I know that similar questions have been asked before but I still wasn't able to find answers to all my questions.

In many proofs in complexity theory we use an enumeration of some $T(n)$-time Turing machines. For simplicity, let's consider polynomial-time TM's. I want to know exactly how we construct such an enumeration.

I know that the following observations are important:

  • TM's correspond to the natural numbers: each binary sequence (natural number) encodes some Turing machine (if we have a sequence that does not encode a valid TM, we say that it is a trivial machine that halts and rejects on all inputs immediately)

  • Every TM's is represented by infinitely many strings/natural numbers, because we allow the encoding to end with any number of 0's (that do not matter for the encoding).

So if we want to obtain an enumeration of TM's that halt in polynomial time for some input $x \in \{0,1\}^n$, we can let each TM of our enumeration of all TM's (the natural numbers) run on input $x$, but then with a counter and an extra tape. If the TM hasn't halted in $n^i + i$ steps, with $i$ the length of the sequence that encodes the TM, we remove it from our enumeration. Because every TM is represented by an infinite number of strings, we now have any TM that runs in time $O(n^c)$ for some $c$.

Please tell me if this is not correct.

My confusion lies here: we need TM's that run in polynomial time for all inputs. Do we need to go over all possible inputs? There are only finitely many inputs of length $n$, but how are we sure that some TM does not use more than polynomial time for a larger input? Or is this some trivial consequece from the deterministic nature of Turing machines?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The simplest way is to use timed Turing machines. We enumerate pairs $\langle T_i, P_j \rangle$, where $T_i$ goes over all Turing machines, and $P_j$ goes over all polynomials. The machine corresponding to $\langle T_i, P_j \rangle$ simulates $T_i$ for $P_j(n)$ time steps, and then stops it (unless it already halted).

This is better than your solution, since you have to verify that the given Turing machine runs in time $P(n)$ for some given polynomial, a task which is uncomputable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I'm sorry, but I still do not quite understand. Is there even an algorithm that produces an enumeration of poly-time TM's? There are both infinitely many T_i's as P_j's, and I see how we could go over these simultaniously with some technique similar to Levin's Universal Search or something. But don't we need to be sure that the TM runs in poly-time for all possible inputs of any length? How can we start producing a list without going over all possible inputs? $\endgroup$
    – Mal
    Commented Apr 26, 2017 at 9:20
  • $\begingroup$ You don't need Levin's universal search. You can enumerate separately all Turing machines and all polynomials, and given this it is not hard to enumerate them together. We then interpret a pair $\langle T_i, P_j \rangle$ as a Turing machine which runs $T_i$ up to time $P_j(n)$ (where $n$ is the input length). This is always a polytime Turing machine. On the other hand, if $T_i$ is a polytime Turing machine, then it always stops after time $P_j$, and so $\langle T_i,P_j \rangle$ is equivalent in operation to $T_i$. $\endgroup$
    – Yuval Filmus
    Commented Apr 26, 2017 at 15:35
  • $\begingroup$ It is your approach that requires us to somehow check whether a given Turing machine runs in polytime. My approach has no such restrictions. $\endgroup$
    – Yuval Filmus
    Commented Apr 26, 2017 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.