Why aren't recursively enumerable languages undecidable

user602774 picture user602774 · Feb 26, 2012 · Viewed 8.5k times · Source

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

Dan Hulme picture Dan Hulme · Feb 26, 2012

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.