Register

Materials:

Recent questions tagged decidability

14 votes
2 answers
395
GATE CSE 1987 | Question: 2m
State whether the following statements are TRUE or FALSE: The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.
State whether the following statements are TRUE or FALSE:The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.
User Avatar
14 votes
4 answers
396
GATE CSE 1987 | Question: 2l
State whether the following statement are TRUE or FALSE. $A$ is recursive if both $A$ and its complement are accepted by Turing machines.
State whether the following statement are TRUE or FALSE.$A$ is recursive if both $A$ and its complement are accepted by Turing machines.
User Avatar
0 votes
1 answer
399
NPC Problems
User Avatar
5 votes
0 answers
400
UNDECIDABLE
User Avatar
2 votes
1 answer
401
class of language
1. L = {<M>|M is a TM and L(M) is countable} 2. L = {<M>|M is a TM and L(M) is uncountable} what is the class of 1 and 2 recursive/RE/NOT RE
1. L = {<M>|M is a TM and L(M) is countable}2. L = {<M>|M is a TM and L(M) is uncountable}what is the class of 1 and 2 recursive/RE/NOT RE
User Avatar
2 votes
1 answer
402
Halting Problem
User Avatar
0 votes
0 answers
403
Decidability ME test series
Which of the following language is decidable? a. {(M)| M is a TM and there exist an input whose length is less than 100, on which M halts} b. {(M)| M is a TM and L(M) = {00, 11}} c. Both (a) and (b) d. None of the above
Which of the following language is decidable?a. {(M)| M is a TM and there exist an input whose length is less than 100, onwhich M halts}b. {(M)| M is a TM and L(M) = {00,...
User Avatar
2 votes
1 answer
404
Decidability
i m confused between 2 problems 1. X={M| L(M)=ε} 2. Y ={M| M accepts ε} where M is Turing Machine is this 2 problems are different and also explain decidability of both ie. decidable/semi-decidable/undecidable....
i m confused between 2 problems 1. X={M| L(M)=ε} 2. Y ={M| M accepts ε}where M is Turing Machineis this 2 problems are different and also explain decidability of both...
User Avatar
0 votes
0 answers
405
decidability
1. I know that whether a cfg generates regular language is undecidable .... somone plzz help me to prove that whether a given cfl is regular language also undecidable .... 2. how equvilance problem on 2 dcfl is decidable??
1. I know that whether a cfg generates regular language is undecidable ....somone plzz help me to prove thatwhether a given cfl is regular language also undecidable .......
User Avatar
5 votes
2 answers
410
Halting Problem of Turing Machines
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
User Avatar
1 votes
1 answer
411
TOC-decidability
If L1 <= L2 In which of the following cases it is undecidable? A. L1 and L2 are DCFL's B. L1 and L2 are recursive C. L1 and L2 are regular D. Both A and B
If L1 <= L2In which of the following cases it is undecidable?A. L1 and L2 are DCFL'sB. L1 and L2 are recursiveC. L1 and L2 are regularD. Both A and B
User Avatar
0 votes
1 answer
417
Virtual Gate Test Series: Theory Of Computation - Decidable Language
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$ (C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$ (D) $L^R$ is decidable
$L$ is surely decidable if (A) both $L$ and its complement are not recognizable (B) $L \subseteq \{0\}^*$(C) $L \leq_m \{0^n1^n\;\mid\;n\geq0\}$(D) $L^R$ is decidable
User Avatar
0 votes
0 answers
418
Partially Decideable 1,1
Some explanation?
Some explanation?
User Avatar
Page: