Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
