Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

closed as too localized by Mark Sapir, Daniel Litt, Mariano Suárez-Alvarez, Andres Caicedo, Pete L. Clark Mar 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.

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

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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