Prove that if L is a recursive language, then its complement Ls is also recursive

1.1k Views Asked by At

Considering that a language $L$ is recursive iff there exist a Turing machine $T$ that accepts every string of the language $L$ and rejects all strings that don't match the alphabet of $L$.

In other words, if string $S$ is part of the alphabet of language $L$, then the turing machine $T$ will accept it and halts, otherwise the turing machine halts without ever reaching an accepting state.

I've already been working in this proof:

$L$ is a language accepted by a turing machine that halts on all inputs. We construct a turing machine Ts from $T$. turing machine $T$ given an input string $S$ enters into an accepting state then Ts rejects and halts for string $W$. Also, if the turing machine $T$ halts without accepting $W$, Ts enters into an accepting state. Ts accepts strings that are not accepted by $T$. Therefore, Ts recognizes the complement of $L$.

But I want to show the next "if language $L$ is accepted by Turing $T$ then it is rejected by $T_s$ and if it is accepted by Ts then it is rejected by T" And conclude that $L(T_s)=L_s$ Therefore $L_s$ is recursive.

Any ideas?