15
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ The esablished terminology is computably enumerable. Many people will say that "countable" and "enumerable" are synonyms. I edited the question accordingly. $\endgroup$ – Andrej Bauer Sep 22 '17 at 18:09
  • $\begingroup$ @AndrejBauer, computably and recursive are synonims, right? $\endgroup$ – rus9384 Sep 22 '17 at 18:43
  • 1
    $\begingroup$ @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... $\endgroup$ – David Tonhofer Sep 23 '17 at 18:09
23
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ @JorgePerez No and no. $\endgroup$ – David Richerby Sep 22 '17 at 21:01
  • 3
    $\begingroup$ This proves existence, but doesn't give an example.. $\endgroup$ – BlueRaja - Danny Pflughoeft Sep 23 '17 at 1:06
  • 2
    $\begingroup$ @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. $\endgroup$ – Wildcard Sep 23 '17 at 1:26
  • 2
    $\begingroup$ 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$. $\endgroup$ – orlp Sep 23 '17 at 6:48
  • 7
    $\begingroup$ @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. $\endgroup$ – Tanner Swett Sep 23 '17 at 12:11
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Aren't there languages with uncountable complexity? $\endgroup$ – rus9384 Sep 22 '17 at 18:50
  • $\begingroup$ @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). $\endgroup$ – David Richerby Sep 22 '17 at 19:14
  • $\begingroup$ @DavidRicherby, well, jmite claims that every undecidable problem operates with finite strings? I think that holds only for every Turing-recognizable undecidable problem. $\endgroup$ – rus9384 Sep 22 '17 at 19:19
  • $\begingroup$ @rus9384 Any language over a finite alphabet is countable, and computability usually ignores infinite alphabets. See also this question. $\endgroup$ – jmite Sep 22 '17 at 19:39
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Sep 22 '17 at 20:30
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – David Richerby Sep 22 '17 at 18:25
  • $\begingroup$ @DavidRicherby couple weeks ago you claimed me the opposite in the comments to Yuvals answer. And this is not the first similar case. $\endgroup$ – fade2black Sep 22 '17 at 18:27
  • $\begingroup$ 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! $\endgroup$ – David Richerby Sep 22 '17 at 18:31
  • 3
    $\begingroup$ @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)? $\endgroup$ – rus9384 Sep 22 '17 at 18:45
  • $\begingroup$ @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. $\endgroup$ – David Richerby Sep 22 '17 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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