# 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?

• No. There are only countably many Turing machines, but uncountably many subsets of say, $\mathbb{N}$. 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. Mar 9 '11 at 5:25

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.