Register

Materials:

Recent questions tagged decidability

0 votes
0 answers
122
Peter Linz Edition 5 Exercise 12.2 Question 2 (Page No. 311)
Show that the two problems mentioned at the end of the preceding section, namely $\text(a)$ $L(M)$ contains any string of length five, $\text(b)$ $L(M)$ is regular, are undecidable.
Show that the two problems mentioned at the end of the preceding section, namely$\text(a)$ $L(M)$ contains any string of length five,$\text(b)$ $L(M)$ is regular,are unde...
User Avatar
0 votes
0 answers
126
Peter Linz Edition 5 Exercise 12.1 Question 14 (Page No. 308)
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines with this $\Gamma$.
Consider the set of all $n-$state Turing machines with tape alphabet $\Gamma = \{0,1,\square\}$. Give an expression for $m(n)$, the number of distinct Turing machines wit...
User Avatar
1 votes
1 answer
127
Peter Linz Edition 5 Exercise 12.1 Question 13 (Page No. 308)
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
Let $B$ be the set of all Turing machines that halt when started with a blank tape. Show that this set is recursively enumerable, but not recursive.
User Avatar
0 votes
0 answers
130
Peter Linz Edition 5 Exercise 12.1 Question 10 (Page No. 308)
Let $M$ be any Turing machine and $x$ and $y$ two possible instantaneous descriptions of it. Show that the problem of determining whether or not $x \vdash^{*}_M y$ is undecidable.
Let $M$ be any Turing machine and $x$ and $y$ two possible instantaneous descriptions of it. Show that the problem of determining whether or not $x \vdash^{*}_M y$ is und...
User Avatar
1 votes
0 answers
139
Reduction (ACE)
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizable Then $L_{1}$ cannot be A)not REL B)Context Sensitive C)Context Free ​​​​​​​​​​​​​​D)Recursive
If $L_{1}\preceq L_{2}$ and $L_{2}$ turing recognizableThen $L_{1}$ cannot beA)not RELB)Context SensitiveC)Context Free​​​​​​​​​​​​​​D)Recursi...
User Avatar
0 votes
0 answers
140
#TOC #GeneralGuidance
I am new to the topic of TOC and finding it difficult to develop intuition for questions. Though,I am good with Mathematics and someone told TOC is mathematical concept. How should I study TOC specifically?
I am new to the topic of TOC and finding it difficult to develop intuition for questions.Though,I am good with Mathematics and someone told TOC is mathematical concept. H...
User Avatar
1 votes
0 answers
141
GO_DecidabilitySlides
This is from GO Decidability slides. I have a doubt with 3 & 4 which is saying every TM ACCEPT L since accepted implies that it rejects all which is not part of language.Why we are using ACCEPTED instead of the word RECOGNISED?
This is from GO Decidability slides.I have a doubt with 3 & 4 which is saying every TM ACCEPT L since accepted implies that it rejects all which is not part of language.W...
User Avatar
1 votes
1 answer
143
Turing Machines Theory
What is the difference between Turing Recognizable and Turing Decidable? Thanks!
What is the difference between Turing Recognizable and Turing Decidable?Thanks!
User Avatar
1 votes
3 answers
145
Gateforum mock 2
User Avatar
0 votes
0 answers
148
Decidability
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$ I was unable to get proof given in pdf above.Can anyone explain, if someone got it.
From http://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf $L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$I was unable to get...
User Avatar
0 votes
1 answer
150
toc(undecidability)
does intersection and complement problem of CSL language follow closure property? does intersection and complement problem of CSL language are decidable?
does intersection and complement problem of CSL language follow closure property? does intersection and complement problem of CSL language are decidable?
User Avatar
Page: