Recent questions tagged decidability

2 votes
0 answers
152
CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty}Which of the following is true?a- Decidable RECB- Undecidable and REc-Undecidable and non REd- Decidable ...
0 votes
0 answers
153
The problem of finding an integral solution of a given system of integral polynomial equations has complexity:Polynomial-timeExponential-spaceUndecidableExponential-time
0 votes
0 answers
158
CFG G=(N,Σ,P,S) and a string x∈Σ∗, does x∈L(G)} ?Is it Decidable?
1 votes
1 answer
159
0 votes
1 answer
161
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
1 votes
1 answer
164
M is a TM and L(M) does not accepts 00 and 11.M is a TM and L(M) is countable . RE or NOT RE?
0 votes
0 answers
165
L={ <M | ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS }here what can we say about ‘L’?
1 votes
1 answer
168
1 votes
1 answer
169
0 votes
1 answer
170
2 votes
1 answer
172
If L is CFL then $\bar{L}$ is Recursive. ( True/False)If L is CFL then $\bar{L}$ is RE. (True/Flase).
0 votes
0 answers
173
Which one is True?$1)$ A set $S$ , some of it’s elements creates injective function. Then S is decidable$2)$ A bijective function can be $NP$ Hard$3)$ A function which...
0 votes
1 answer
174
L= { M⟩|L(M) accepts empty string} L={⟨M⟩|TM halts on empty string} Identify RE , REC , Not RE ??Are this two languages or sameI think both are same if TM halts on...
0 votes
0 answers
176
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?
1 votes
0 answers
177
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?
0 votes
0 answers
180