Timeline for How to construct a sequence of polynomial-time Turing machines
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2017 at 8:52 | vote | accept | Mal | ||
| Apr 26, 2017 at 15:35 | comment | added | Yuval Filmus | It is your approach that requires us to somehow check whether a given Turing machine runs in polytime. My approach has no such restrictions. | |
| Apr 26, 2017 at 15:35 | comment | added | Yuval Filmus | 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$. | |
| Apr 26, 2017 at 9:20 | comment | added | Mal | 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? | |
| Apr 25, 2017 at 20:37 | history | answered | Yuval Filmus | CC BY-SA 3.0 |