Recent questions tagged decidability

which is/are TRUE:1)All recursive lang are decidable problems?2)All decidable problems are recursive language?- is both of them are true? any proof please?

Where can we apply PCP to check, if the grammar is undecidable?Some examples of such grammars Ambiguous grammarAny other example and how they solved with PCP?

Here is my analysis.P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes f...

$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{L}_1 = \{\text{<M>}|\text{M is a TM and L(M) is infinite} \}$Not RE$\text{L}_2 = \{ \text{<M>} | \text{M is a TM and L(M) is countable} \}$and $\text{L}_3 = \{ \t...

Given two deterministic CFG G$_1$ and G$_2$ , is L(G$_1$) ∩ L(G$_2$) = ∅ ?

L1:{<M | there exist a Turing machine M' such that <M>$\neq$<M' and L(M) = L(M')}How this problem becomes trivial? and if it non-trivial then please explain why is that s...

A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?

Given a turing machine M ,state q, and string 'w'whether M ever moves its head to the left when started with input wis decidable or undecidable ? explain ?

Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape.how the above problem is solvable?somewhere...

$D = \left \{ <M \mid \ M \text{ is a TM that rejects the input string } x \right \}$What is complement of D and is it Decidable, Turing recognizable or not Turing recogn...

A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL