Enumerate over all halting Turing Machines?

Question

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.

Answer 1

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.}

Answer 2

If you mean halting TMs by TMs that are halt on all strings, then yes, it is impossible to enumerate over all halting TMs. However, this is not because the set of halting TMs is undecidable, but because it is even not recognizable. Note there exists a TM enumerating all valid strings of a language if and only if the language is recognizable.

The word "enumeration" in the paper you linked to is different from our common understanding of an enumerator. Or rather, it means an infinite sequence of halting TMs, and is not required to contain all halting TMs.