Show that if some language L and its complement L are both T

Show that, if some language L and its complement L are both Turing-recognizable, then this means that L is also decidable.

Solution

AIM: The language L is decidable.

Proof: We have a theorem that if a language is decidable iff (if and only if) L and its complement are Turing recognizable.

i.e. If an lnguage is decidable then its complement is also decidable. (By clousure property of complementation)

In other direction, Let L and L\' be recognizable by M1 and M2 respectively. Now we\'ll construct M that decides L.

M:= For i/p w, set n=1,

Simulate M1 on w for n steps, if accepts, then accept string.

Simulate M2 on w for n steps, if rejects, then reject string.

Increase n and goto 1

Either w belongs to L, w belongs L\', both will halts in finite number of steps in a tape.

Therefore M halts in finite number of steps.

So hence proved