0
$\begingroup$

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?

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

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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