# Is it true that a set is countable if and only if there exists a Turing machine to enumerate all the elements in the set? [closed]

In many textbooks, it is said that a set is countable if we can list the elements as $a_1, a_2, \dots$.

My question is: is it true that a set is countable if and only if there exists a Turing machine to enumerate (without termination) all the elements in the set?

-

## closed as too localized by Mark Sapir, Daniel Litt, Mariano Suárez-Alvarez♦, Andrés Caicedo, Pete L. ClarkMar 9 '11 at 6:50

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

No. There are only countably many Turing machines, but uncountably many subsets of say, $\mathbb{N}$. –  Kevin Ventullo Mar 9 '11 at 5:09
This question would probably be better suited to math.stackexchange.com, by the way — it’s not really a research-level question, which is what mathoverflow is intended for. –  Peter LeFanu Lumsdaine Mar 9 '11 at 5:25

No.

Consider the set of all pairs $(x,n,i)$, where: $x$ is the code for a Turing machine $T_x$; $n$ is a natural number; and either $i=1$ and $T_x$ halts on input $n$, or $i=0$ and $T_x$ diverges on $n$.

This set is certainly countable (it’s isomorphic to $\mathbb{N}^2$, just by forgetting the $i$-component). But if we had a Turing machine that enumerated it, then we’d have solved the halting problem: given any code $x$ and input $n$, to work out if it halts, just wait until the machine spits out either $(x,n,0)$ or $(x,n,1)$. (Formally: write a new Turing machine to simulate the running of the first one and “watch” for an appropriate value appearing.)

Generally, subsets of $\mathbb{N}$ that can be given in the manner you describe are called computably enumerable, or recursively enumerable. It’s a fundamental concept of computability theory; it’s a much stronger notion than countability.

Also note that countability is defined as a predicate on abstract sets; it’s not clear what computable enumerability of a set means in the abstract, only for subsets of $\mathbb{N}$ and similarly presented objects.

-

I would say no. If there is such a machine then the set is obviously countable. But for the other direction, there are many countable subsets of non computable real numbers. Unless you relax sufficiently your definition of enumeration (What finite string would the Turing machine output to represent a non computable number, or any irrational number for that matter?) then I don't see how such a Turing machine could enumerate any of these sets.

-