0
$\begingroup$

Consider below two languages

$L_1=\{<M>|$ M is a turing machine, $M_0$ is a TM that halts on all inputs, and $M_0 \in L(M) \}$

$L_2=\{<M>|$M is a TM, $M_0$ is a TM that halts on all inputs, and $M \in L(M_0)\}$

So, in both languages $M_0$ is a halting Turing machine, so the language of $L(M_0)$ is recursive.

Now in case of $L_1$, it appears to me that $L(M)$ is recursively enumerable, and since recursive languages are proper subset of Recursively Enumerable languages, so $M_0 \in L(M)$ , and since, for the no cases of the language, our turing machine could go into infinite loop, we cannot answer the no case of $L_1$, making $L_1$ Recursively Enumerable but not recursive.

In case of $L_2$, our given machine $M \in L(M_0)$ so it is very sure that the language $L(M)$ should be recursive.

Am I correct in my reasoning.?

PS: I am weak at these RE and REC problems.So, I decided to work on them and discuss my doubts here.None of the above problems are homework problems.

|cite|improve this question
$\endgroup$
  • $\begingroup$ How is $M_0$ quantified in the definition of $L_1$? That is, does the condition hold for some $M_0$? Or for all such $M_0$? $\endgroup$ – dkaeae Jan 3 at 16:04
  • $\begingroup$ i think the reason is substantial to judge for L2 but for L1 its not viable to say that its " Recursive enumerable but not recursive" since the subset of L(M) can be recursive or cannot be which does not provide sufficient evidence on the nature of L(M) apart from that its a turing recognisable thus a "Recursive enumerable language " $\endgroup$ – Noob Jan 4 at 13:08

Your Answer

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

Browse other questions tagged or ask your own question.