3
$\begingroup$

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.

Improve this question
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ It's late and I'm clearly not thinking clearly, but what is the problem with this: Let $k$ run from 1 to infinity. For each $k$, simulate the first $k$ Turing machines at most $k$ steps. If the $n$th Turing machine halts and $n$ has not been output yet, output $n$. $\endgroup$ – JiK Sep 13 '19 at 22:05
  • $\begingroup$ Ah, what I'm missing is probably that "halting TM" in this question means a TM that halts with every input, not TMs without input (or (TM,input)-pairs). $\endgroup$ – JiK Sep 13 '19 at 22:07
3
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ And not required to be produced by a Turing machine. So you can even have an enumeration of all halting TMs in this sense. Even though there's no TM that can produce that enumeration, the enumeration (call it a list, if you prefer) still exists. $\endgroup$ – David Richerby Mar 19 '19 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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