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.