patternMinor
Enumerate over all halting Turing Machines?
Viewed 0 times
allhaltingmachinesturingoverenumerate
Problem
I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the natural numbers and checking whether each number describes a syntactically well-defined TM.
I am wondering how it is possible to enumerate over all halting TMs. My intuition tells me that since the halting problem is undecidable, it should not be possible to filter an enumeration of all TM descriptions to only those TM descriptions which describe halting TMs.
Nevertheless, I recently came across a well-reputed Oded Goldreich and Bernd Meyer, Computational Indistinguishability: Algorithms vs Circuits, Theoretical Computer Science 191(1–2):215–218, 2998) that uses an enumeration of all halting Turing Machines (see Proposition 1, pg. 2). I'd appreciate any help in understanding this.
I am wondering how it is possible to enumerate over all halting TMs. My intuition tells me that since the halting problem is undecidable, it should not be possible to filter an enumeration of all TM descriptions to only those TM descriptions which describe halting TMs.
Nevertheless, I recently came across a well-reputed Oded Goldreich and Bernd Meyer, Computational Indistinguishability: Algorithms vs Circuits, Theoretical Computer Science 191(1–2):215–218, 2998) that uses an enumeration of all halting Turing Machines (see Proposition 1, pg. 2). I'd appreciate any help in understanding this.
Solution
The paper you're referring to is using "enumeration" just to mean "ordered list". Your feeling that such a list can't be computed by a Turing machine is correct. However, the list exists, even though there's no algorithm that will tell us what its members are.
Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of the halting Turing machines". So it's just any ordered list of halting Turing machines, not necessarily all of them. It specifically mentions enumerations of polynomial time Turing machines. You might be surprised that these are enumerable, up to equivalence*. This is because you can turn any Turing machine into a polynomial time Turing machine by picking your favourite polynomial and modifying the machine so it rejects if it hasn't in that many steps. Since you can enumerate all polynomials (say, with nonnegative integer coefficients), and you can enumerate all Turing machines, you can combine the two to enumerate all polynomial time Turing machines.
* Two Turing machines are equivalent if they give the same output for every input.
Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of the halting Turing machines". So it's just any ordered list of halting Turing machines, not necessarily all of them. It specifically mentions enumerations of polynomial time Turing machines. You might be surprised that these are enumerable, up to equivalence*. This is because you can turn any Turing machine into a polynomial time Turing machine by picking your favourite polynomial and modifying the machine so it rejects if it hasn't in that many steps. Since you can enumerate all polynomials (say, with nonnegative integer coefficients), and you can enumerate all Turing machines, you can combine the two to enumerate all polynomial time Turing machines.
* Two Turing machines are equivalent if they give the same output for every input.
Context
StackExchange Computer Science Q#105763, answer score: 4
Revisions (0)
No revisions yet.