418 views
0 votes
0 votes

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

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


for $L_1$, $M$ accepts all encodings of TM which halts on all inputs. So this language is infinite because $\exists$ infinite number of TM's which accept $\Sigma^*$. 

Now $L(M)$ is not even RE. If that then how $L_1$ is RE.

Please explain both. 

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
aditi19 asked Oct 29, 2018
250 views
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
0 votes
0 votes
0 answers
4
sushmita asked Dec 23, 2016
409 views
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems...