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?



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?
**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.


