0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Wandering Logic May 8 '14 at 22:00
  • 1
    $\begingroup$ "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. $\endgroup$ – Raphael May 8 '14 at 22:59
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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." $\endgroup$ – David Richerby May 9 '14 at 0:21
  • $\begingroup$ 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. $\endgroup$ – jmite May 9 '14 at 5:08
  • $\begingroup$ 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. $\endgroup$ – David Richerby May 10 '14 at 3:49

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