snippetMinor
How to construct a sequence of polynomial-time Turing machines
Viewed 0 times
polynomialtimesequencemachineshowturingconstruct
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#74517, answer score: 3
Revisions (0)
No revisions yet.