Editing Computability (section)

==== Beyond recursively enumerable languages ====
The halting problem is easy to solve, however, if we allow that the Turing machine that decides it may run forever when given input which is a representation of a Turing machine that does not itself halt.  The halting language is therefore recursively enumerable.  It is possible to construct languages which are not even recursively enumerable, however.

A simple example of such a language is the complement of the halting language; that is the language consisting of all Turing machines paired with input strings where the Turing machines do ''not'' halt on their input.  To see that this language is not recursively enumerable, imagine that we construct a Turing machine ''M'' which is able to give a definite answer for all such Turing machines, but that it may run forever on any Turing machine that does eventually halt.  We can then construct another Turing machine <math>M'</math> that simulates the operation of this machine, along with simulating directly the execution of the machine given in the input as well, by interleaving the execution of the two programs.  Since the direct simulation will eventually halt if the program it is simulating halts, and since by assumption the simulation of ''M'' will eventually halt if the input program would never halt, we know that <math>M'</math> will eventually have one of its parallel versions halt.  <math>M'</math> is thus a decider for the halting problem.  We have previously shown, however, that the halting problem is undecidable.  We have a contradiction, and we have thus shown that our assumption that ''M'' exists is incorrect.  The complement of the halting language is therefore not recursively enumerable.