consisting of all Turing machine descriptions paired with all possible input streams on which those Turing machines will eventually halt, is not recursive. The halting problem is therefore called non-computable or undecidable.

An extension of the halting problem is called Rice's theorem, which states that it is undecidable (in general) whether a given language possesses any specific nontrivial property.

Beyond recursively enumerable languages

1.Previous
3.Next