Why aren't recursively enumerable languages undecidable

Question

This is the definition of decidable from Wikipedia

In computability theory, an undecidable problem consists of a family of instances for which a particular yes/no answer is required, such that there is no computer program that, given any problem instance as input, terminates and outputs the required answer after a finite number of steps. More formally, an undecidable problem is a problem whose language is not a recursive set

The recursive set is a subset of the recursively enumerable one. There are some recursively enumerable languages that are outside the recursive set. So why aren't recursively enumerable languages undecidable?

Answer 1

Recursively enumerable languages/sets are also known as semi-decidable. They aren't decidable, because there isn't a machine that looks at the input and says yes or no (correctly). Semi-decidable means you can write a machine that looks at the input and says yes if the input is in the set, or fails to halt if the input is not in the set. Semi-decidable turns out to be equivalent to recursively enumerable in the same way that decidable is equivalent to recursive:-

If you have a Turing machine R that enumerates a recursively enumerable language, you can make a new machine D that takes an input that may or may not be in the language/set. D runs R until R outputs the first element of the set, and then D compares that with its input. If they match, it returns a "yes" result. If they don't match, it continues running R until it gets the next element, and so on. Since R never halts (because the language is only recursively enumerable, not recursive), D will either answer yes or not halt.

Conversely, if you have a Turing machine D that answers yes or fails to halt, you can make a new machine R which uses the usual technique to run several instances of D in parallel one step at a time with various inputs: all the elements which may or may not be in the set. Every time one of the parallel executions of D halts with a "yes" answer, R outputs that input of D, and continues executing D on all the remaining inputs. R will never halt (because there are some inputs on which D will not halt), but eventually it will output every element for which D answered "yes", that is, every element in the set/language.

Don't get confused into thinking there are three (disjoint) kinds of sets: decidable, semi-decidable, and undecidable. There are two kinds: decidable and undecidable. All of the decidable sets are also semi-decidable (though it's unusual to say it that way). Some of the undecidable sets are also semi-decidable. This is just the same as saying that all enumerable sets are recursively enumerable, and some non-enumerable sets are recursively enumerable.

Answer 2

A semidecidable problem (or equivalently a recursively enumerable problem) could be:

1. Decidable: If the problem and its complement are both semidecidable (or recursively enumerable), then the problem is decidable (recursive).

2. Undecidable: If the problem is semidecidable and its complement is not semidecidable (that is, is not recursively enumerable).

Important note: Remember that a decidable (recursive) problem is also semidecidable (recursively enumerable). Conversely, if a problem is not recursively enumerable (semidecidable), then is not recursive (decidable).

What the Wikipedia entry says is that:

Partially decidable problems THAT ARE NOT DECIDABLE are called undecidable.

In general, a semidecidable problem (recursively enumerable) could be decidable (recursive) or undecidable (nonrecursively enumerable).

Also note that a problem and its complement could both (or just one of them) be not even semi-decidable (nonrecursively enumerable). Also note that, if a problem is recursive, its complement is also recursive.