# Recent questions tagged decidability

2 answers 12 views
L=a language M= a TM Lc= complement of L 1) L={<M> | M is a TM, encoded with some alphabet } ; L is recursive 2) L=set of all cfls generated by some cfg; => L is recursive enumerable but not recursive , Lc is not Recursive ... is Recursively Enumerable but Not Recursive I BELIEVE THE ABOVE STATEMENTS TO BE TRUE / CORRECT please somebody verify and reply please do reply ASAP THANKING YOU.
0 answers 15 views
3 answers 29 views
Is it decidable that a Turing Machine will ever leave the start state on any input?
Let G1 be a context free grammar and G2 a regular grammar. Is the problem decidable? $L(G1) \cap L(G2)= \phi$ Let L1 be a regular language and G a context free grammar. Is the problem decidable? $L1\subseteq L(G)$ 3. Let G1 and G2 be grammars with G1 regular. Is the problem decidable when: $L(G1)=L(G2)$ * G2 is unrestricted * G2 is context free * G2 is regular?
$L = \{ <M> | \text{M is a TM that halts on all inputs and L(M) = L’ for some undecidable language L’} \}$ Then $L$ is decidable and recursive decidable and non-recursive undecidable and recursively enumerable undecidable and non-recursively enumerable
For the following language, state whether language is (I) recursive, (II) recursively enumerable but not recursive, or (III) not recursively enumerable. Prove your answer. $L_{11} = \{<M_{1}, M_2> | \text{ M}_1 \text{and M}_2 \text{ are two TMs}, \text{and } \epsilon \in L(M_1) \backslash L(M_2) \}$