Register

Materials:

Recent questions tagged decidability

0 votes
0 answers
364
decidability doubt
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??
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...
User Avatar
3 votes
1 answer
366
doubt
Which of the following is RE / NOT RE ? I.<M>|M is a TM that accepts all even numbers. II.<M>|M is a TM that does not accept all even numbers. II.<M>|M is a TM rejects all even numbers.
Which of the following is RE / NOT RE ?I.<M>|M is a TM that accepts all even numbers.II.<M>|M is a TM that does not accept all even numbers.II.<M>|M is a TM rejects all e...
User Avatar
0 votes
1 answer
369
Given a Turing machine M, does M halt on the empty tape?
Given a Turing machine M, does M halt on the empty tape? ----reading more and more on TM,i am getting confused.please clarify whther it is R.E or non R.E..?? does empty tape means empty string or NO INPUT??
Given a Turing machine M, does M halt on the empty tape? reading more and more on TM,i am getting confused.please clarify whther it is R.E or non R.E..??does empty tape ...
User Avatar
8 votes
3 answers
371
L= {<TM> | TM halts on every input}
$L=\left \{ <TM> | TM\ halts\ on\ every\ input\ \right \}$ is above language Recursively enumerable or non recursively enumerable??
$L=\left \{ <TM | TM\ halts\ on\ every\ input\ \right \}$is above language Recursively enumerable or non recursively enumerable??
User Avatar
3 votes
0 answers
372
decidability
Is equality problem for DCFL is decidable if yes then how to prove?
Is equality problem for DCFL is decidable if yes then how to prove?
User Avatar
2 votes
1 answer
373
decidability
a context-free grammar is ambiguous is undecidable But for a given context-free language if we can make more than one parse tree then it means that it is ambiguous..So how it is undecidable??
a context-free grammar is ambiguous is undecidableBut for a given context-free language if we can make more than one parse tree then it means that it is ambiguous..So how...
User Avatar
1 votes
0 answers
374
Decidability+TM
I dont get how the first is decidable and I have no idea about other two. Detailed explanation would be helpful
I dont get how the first is decidable and I have no idea about other two. Detailed explanation would be helpful
User Avatar
0 votes
1 answer
377
decidability
intersection of two recursive lang is recursive is this problem decidable or not?
intersection of two recursive lang is recursive is this problem decidable or not?
User Avatar
0 votes
1 answer
378
Doubt on decidability
Are these 2 problems different? 1. Given grammar G, is G regular? 2. Given grammar G, is L(G) regular? Which of these 2 are decidable?
Are these 2 problems different?1. Given grammar G, is G regular?2. Given grammar G, is L(G) regular?Which of these 2 are decidable?
User Avatar
0 votes
2 answers
380
MadeEasy Test Series: Theory Of Computation - Decidability
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable? Please explain.
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable?Please explain.
User Avatar
17 votes
1 answer
381
How to Check For Partial Decidability
What is Partial Decidability ? How do we check whether a problem is Partialy Decidable or Not ?
What is Partial Decidability ? How do we check whether a problem is Partialy Decidable or Not ?
User Avatar
–2 votes
0 answers
382
General TOC decidable problems
How to solve decidable problems and undecidable problems.......Its getting very difficult to understand....??
How to solve decidable problems and undecidable problems.......Its getting very difficult to understand....??
User Avatar
0 votes
1 answer
383
decidability 
Decidability of M is a TM and L(M) is a regular language ?
Decidability of M is a TM and L(M) is a regular language ?
User Avatar
0 votes
0 answers
386
Recursively Enumerable or not?
What is the class of the following languages? RE or REC or Not RE? La = {M | M is a Turing machine that halts on exactly 2016 input strings}. Lb = {M | M is a Turing machine that halts on atleast 2016 input strings}.
What is the class of the following languages? RE or REC or Not RE?La = {M | M is a Turing machine that halts on exactly 2016 input strings}.Lb = {M | M is a Turing machin...
User Avatar
46 votes
2 answers
387
GATE CSE 1990 | Question: 3-vii
It is undecidable whether: An arbitrary Turing machine halts after $100$ steps. A Turing machine prints a specific letter. A Turing machine computes the products of two numbers None of the above.
It is undecidable whether:An arbitrary Turing machine halts after $100$ steps.A Turing machine prints a specific letter.A Turing machine computes the products of two numb...
User Avatar
4 votes
2 answers
390
What is the difference ??
Please explain clearly?
Please explain clearly?
User Avatar
Page: