How can a problem be undecidable yet enumerable? [duplicate]

How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers and can be computed by a program with an output. But if thats the case it should be decidable. Or is decidability separated from computability?

Am I misunderstanding the intuition of the halting set?

• Yes, you are misunderstanding. The non-halting set is not recursively enumerable. The halting set can be recursively enumerated, but the decision problem would require that both the halting set and the non-halting set are recursively enumerable. May 8 '14 at 22:00
• "Enumerable means it can be computed, ie ... can be computed by a program with an output. But if thats the case it should be decidable." -- You need to revisit the definitions.
– Raphael
May 8 '14 at 22:59

For me, the easiest way to think of it is this:

You're asking yourself "out of a bunch of candidates in a set $X$, do any of them fulfill the property $P$"?

Decidable/recursive means that you only need to look at a finite number of elements of $X$ before you hit some point where you know nothing that's left has the property.

A problem that's recursively enumerable, but not recursive, is one where you can look at each $x$ in $X$ one at a time. If you find one, then you're done, you know there exists on that fulfills your property. But there's no way of knowing when you're done, and $X$ is infinite, so if one doesn't exist, you will end up searching forever.

This contains some simplifications over the theoretical definitions, so be careful.

As an example: The halting problem is, you're looking at all $x_1, x_2, \ldots$ where each $x_i$ is a configuration of the turing machine $M$ after $i$ steps. The property is, is $x_i$ in a halting state. If you find one, you're done, but if you don't find one, there's no way to know when you're done.

Compare this to the SAT problem. You've got a Boolean formula, and you want to give each variable a True or False value to make the whole thing true. Even though it's really slow, you can try all true/false combinations. There's an exponential number of them, but it's finite. When you're done, you're done, and if none of them satisfied, you can halt, confident that there's no answer.

• "Decidable/recursive means that you only need to look at a finite number of elements of X before you hit some point where you know nothing that's left has the property." No, that's a finite set. The set of even numbers, for example, is decidable but after looking at any finite amount of stuff, you can never say "There are no more even numbers." May 9 '14 at 0:21
• Note that $X$ isn't the language, it's the search space. If you want to accept the set of all even numbers, your "search space" is trivially a singleton: the remainder when dividing by 2. May 9 '14 at 5:08
• You need to make that way clearer, and you need to do it in the answer, not the comments. Up to the point that I quote, you don't even hint that you're talking about some separate search space. May 10 '14 at 3:49