Prove that a language L is recursively enumerable if and onl

Prove that a language L is recursively enumerable if and only if it can be expressed as L = {x | y such that (x, y) R] where R is a decidable language. You need to prove that every language of this form is recursively enumerable, and that every recursively enumerable language can be described as above for some decidable language R.

Solution

Recursively enumerable languages are also known as type 0 languages.

Let L be a language. Then L is recursively enumerable if there exists a TM M such that L = L(M).

If L is r.e. then L = L(M) for some TM M, and
If x is in L then M halts in a final (accepting) state.
If x is not in L then M may halt in a non-final (non-accepting) state or no transition is available, or loop forever.

Let L be a language. Then L is recursive if there exists a TM M such that L = L(M) and M halts on all inputs.

If L is recursive then L = L(M) for some TM M, and
If x is in L then M halts in a final (accepting) state.
If x is not in L then M halts in a non-final (non-accepting) state or no transition is available (does not go to infinite loop).

L(M’) = L(M1) L(M2)
L(M’) is a subset of L(M1) U L(M2)
L(M1) U L(M2) is a subset of L(M’)
M’ always halts since M1 and M2 always halt

   It follows from this that L3 = L1 U L2 is recursive.