How to prove that $L$, where $$L = \{\langle M\rangle: L(M)\text{ is recognizable}\}$$ is decidable? What about $\bar{L}$?


I claim that $L$ is decidable and I will construct a Turing machine to decide $L$.

Let $M$="on input $\langle M' \rangle$
$\quad ACCEPT$ "

Why does $M$ decide $L$? $M$ takes a description of a Turing machine as input and accepts, that is $L(M)=\{ \langle T \rangle \mid T \text{ is a Turing machine}\}$. If the input is not a description of a Turing machine, $M$ rejects. That is, $M$ always halts*.

Now $L=\{ \langle M \rangle \mid L(M) \text{ is recognizable}\}$, but by definition a language is recognizable if there is a Turing machine that recognizes it. Hence $L$ is also the language of all descriptions of Turing machines. Since $M$ always halts and $L(M)=L$, $M$ decides $L$, so $L$ is decidable.

Since $L$ is decidable, $\bar{L}$ is certainly decidable too (on any input we can run $M$ and invert the output, we accept if $M$ rejects and reject if $M$ accepts.

*Note we implicitly assume that a Turing machine can determine if its input string is a description of a Turing machine or not. This is generally a safe assumption since we are free to choose the encoding of the Turing machine and it is certainly possible to choose an encoding such this is the case (e.g, enumerate all Turing machines $TM_1, TM_2,...$ and let $\langle TM_i \rangle=1^i$, that is a string of $i$ ones, then any string of ones can represent a Turing machine).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.