An exercise giving the relationship between recursively enumerable sets and recursive sets.

Suppose both a language L and its complement L' are recursively enumerable. Then there exist Turing machines M and M' such that M halts precisely on inputs from L, and M's halts precisely on inputs from L'. Consider a Turing machine N which takes as input a word x simulates the runs of M(x) and M'(x) "simultaneously" (i.e. it performs one step of each computation in some interleaved manner). Obviously, (exactly) one of the computations will terminate (either x is in L or it's in L'!). N outputs `1' (x∈L) if M(x) terminates, and `0' if M'(x) does.

Hence L is recursive: N decides membership of L.

Log in or register to write something here or to contact authors.