# Are there any countable sets that are not computably enumerable?

A set is countable if it has a bijection with the natural numbers, and is computably enumerable (c.e.) if there exists an algorithm that enumerates its members.

Any non-finite computably enumerable set must be countable since we can construct a bijection from the enumeration.

Are there any examples of countable sets that are not computably enumerable? That is, a bijection between this set and the natural numbers exists, but there is no algorithm that can compute this bijection.

• The esablished terminology is computably enumerable. Many people will say that "countable" and "enumerable" are synonyms. I edited the question accordingly. Sep 22, 2017 at 18:09
• @AndrejBauer, computably and recursive are synonims, right? Sep 22, 2017 at 18:43
• @rus9384 Yes. Regarding vocabulary, clarity should reign, as Robert Irving Soare writes in Turing-Post Relativized Computability and Interactive Computing (2011): By 1995 the confusion had become intolerable. I wrote an article on Computability and Recursion for the Bull. of Sym. Logic (1996) on the history and scientific reasons for why we should use “computable” and not “recursive” to mean “calculable.” “Recursive” should mean “inductive” as it had for Dedekind and Hilbert. At first, few were willing to make such a change... Sep 23, 2017 at 18:09

Are there any examples of countable sets that are not enumerable?

Yes. All subsets of the natural numbers are countable but not all of them are enumerable. (Proof: there are uncountably many different subsets of $\mathbb{N}$ but only countably many Turing machines that could act as enumerators.) So any subset of $\mathbb{N}$ that you already know is not recursively enumerable is an example – such as the set of all numbers coding Turing machines that halt for every input.

• @JorgePerez No and no. Sep 22, 2017 at 21:01
• This proves existence, but doesn't give an example.. Sep 23, 2017 at 1:06
• @BlueRaja-DannyPflughoeft, giving an example is the same as enumerating one. "Can you give an example of something you can't give an example of? No? Therefore there is nothing you can't give an example of." That's mathematical constructivism in a nutshell. Sep 23, 2017 at 1:26
• Would the image of the busy beaver function $\Sigma$ be such a set? Since $\Sigma$ is strictly increasing it trivially forms a bijection with $\mathbb{N}$, but there is no Turing machine that can enumerate $\Sigma$.
– orlp
Sep 23, 2017 at 6:48
• @Wildcard No, giving an example is the same as defining one, isn't it? There are sets which can be defined but cannot be enumerated by an algorithm, such as the set of all Turing machines that do not halt. Sep 23, 2017 at 12:11

Yes, every undecidable (not semi-decidable) language has this property.

For example, consider the set $L = \{(x,M) \mid M \text{ does not halt on input } x \}$.

Suppose we have an algorithm that can enumerate the members of this set. If such an algorithm existed, we could use this to solve the halting problem with inputs $x,M$, with the following algorithm:

• Alternate between running machine $M$ for $n$ steps on $x$, and enumerating the $n$th member of $L$.

$M$ either halts, or does not halt on $x$. If it halts, eventually we will find an $n$ where we reach a halting state. If it doesn't halt, then eventually we will reach $(M,x)$ in our enumeration.

Thus we have a reduction, and we can conclude that no such enumeration exists.

Note that such enumerations can exist for semi-decidable problems. For example, you can enumerate the set of all halting machine-input pairs by enumerating all possible traces of all Turing Machine executions after $n$ steps, and filter out ones that do not end in a halting state.

• Aren't there languages with uncountable complexity? Sep 22, 2017 at 18:50
• @rus9384 I'm not sure what you mean. "Uncountable" is a measure of size; "complexity" is a measure of how difficult it is to decide. But there are no uncountable languages of finite strings: if you want a language to be uncountable, you must allow infinite strings (or an uncountable "alphabet", or both). Sep 22, 2017 at 19:14
• @DavidRicherby, well, jmite claims that every undecidable problem operates with finite strings? I think that holds only for every Turing-recognizable undecidable problem. Sep 22, 2017 at 19:19
• @rus9384 Any language over a finite alphabet is countable, and computability usually ignores infinite alphabets. See also this question. Sep 22, 2017 at 19:39
• @rus9384 yes, a language is a set of finite strings over a finite alphabet. Any such thing is countable. If you want to get an uncountable language, you need to remove one or both of the instances of "finite" from that definition. But if somebody just says "language", they mean a set of finite strings over some finite alphabet. Sep 22, 2017 at 20:30

In computability theory we deal with subsets of $\Sigma^*$, where $\Sigma = \{0,1\}$. This language is countably infinite, and so any subset $L \subseteq \Sigma^*$ is countable. Furthermore, there are many undecidable but recursively enumerable languages whose complements are not recursively enumerable. These languages are subset of $\Sigma^*$ and hence are countable.

• We don't necessarily deal with binary strings. There are plenty of cases where we might be interested in strings over other alphabets, and people who call computability "recursion theory" tend to deal directly with sets of natural numbers. (That is, the numbers themselves are viewed as primitive, and not encoded as, e.g., binary strings.) Sep 22, 2017 at 18:25
• @DavidRicherby couple weeks ago you claimed me the opposite in the comments to Yuvals answer. And this is not the first similar case. Sep 22, 2017 at 18:27
• Yuval posts a lot of answers, and I post a lot of comments, so you'd have to be more specific. I certainly stand by my comment above, so if I said the opposite at some point, then either I was wrong or confused or you misunderstood me or I was talking about some specific scenario or something like that. I'm sorry if I've confused you, especially if I did it by saying something unclear or incorrect! Sep 22, 2017 at 18:31
• @DavidRicherby, in fact each finite alphabet can be reduced to binary, so, I don't understand how does that matter. Or do we have countably infinite alphabet in this case (where each number has unique symbol)? Sep 22, 2017 at 18:45
• @rus9384 The answer seems to be suggesting that computability theory only considers the alphabet $\{0,1\}$, but that isn't true: it's not even true that computability theory only considers sets of strings. I agree that restricting to binary strings wouldn't make any significant difference to the theory but, for example, it's common to use larger alphabets to make results easier to prove. Sep 22, 2017 at 18:51

I want to give another concrete example. The set of encodings of always halting Turing machines $$R$$ is countable (since there are only countably many Turing machines, halting or non-halting). But $$R$$ itself is not computably enumerable.

Assume $$R$$ were computably enumerable. Then given index $$i$$ we can find the encoding of the always halting Turing machine $$T_i$$ in $$R = \{T_1, T_2, \dots\}$$.

Let's define a Turing machine $$D$$ that accepts the i-th word if and only if $$T_i$$ rejects it and rejects the i-th word if and only if $$T_i$$ accepts it. This Turing machine $$D$$ is also an always halting Turing machine, since we can compute the i-th encoding of the always halting Turing machine $$T_i$$ and simulate it on the i-th word. After $$T_i$$ halts, we just reverse the decision of $$T_i$$.

However, $$D$$ does not appear in the enumeration of always halting Turing machines $$R$$, since for each machine $$T_i$$ it decides differently at least on the i-th input word. This is a contradiction and therefore the assumption that $$R$$ is computably enumerable is false.

So even when we focus on always halting Turing machines can we define a set that is countable but not computably enumerable.

• Note that it's important here that "halting" mean "always halting" - the set of machines that halts on a fixed input is c.e., as is the set of pairs $(M,n)$ of machines $M$ and inputs $n$ such that $M(n)$ halts. May 7, 2023 at 21:41
• Thanks for the suggestion, I've edited my response accordingly. May 9, 2023 at 10:50