The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged decidability
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
0
votes
0
answers
1
Peter Linz Edition 5 Exercise 12.1 Question 9 (Page No. 308)
$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ ... that is, given a pda as in Definition, can we always predict whether or not the automaton will halt on input $w?$
asked
Mar 15
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

17
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
2
Peter Linz Edition 5 Exercise 12.1 Question 7,8 (Page No. 308)
$i)$ Show that there is no algorithm for deciding if any two Turing machines $M_1$ and $M_2$ accept the same language. $ii)$ How is the conclusion of $i$ affected if $M_2$ is a finite automaton$?$
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

21
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 12.1 Question 6 (Page No. 308)
Consider the question: $“$Does a Turing machine in the course of a computation revisit the starting cell $($i.e the cell under the readwrite head at the beginning of the computation$)?$”$ Is this a decidable question$?$
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

24
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
4
Peter Linz Edition 5 Exercise 12.1 Question 5 (Page No. 307)
Show that there is no problem to decide whether or not an arbitrary Turing machine on all input.
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

13
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
5
Peter Linz Edition 5 Exercise 12.1 Question 4 (Page No. 307)
In the general halting problem, we ask for an algorithm that gives the correct answer for any $M$ and $w$. We can relax this generality, for example by looking for an algorithm that works for all $M$ but only a ... that determines whether or not $(M,w)$ halts. Show that even in this restricted setting the problem is undecidable.
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

27
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
6
Peter Linz Edition 5 Exercise 12.1 Question 3 (Page No. 307)
Show that the following problem is undecidable. Given any Turing machine $M, a\in \Gamma $ and $w \in \Sigma^{+}$, determine whether or not the symbol $a$ is ever written when $M$ is applied to $w$.
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

22
views
peterlinz
theoryofcomputation
decidability
proof
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 12.1 Question 2 (Page No. 307)
$\text{Definition:}$ Let $w_M$ be a string that describes a Turing machine $M = (Q,\Sigma,\Gamma,\delta,q_0,\square,F)$, and let $w$ be a string in $M'$s alphabet. We will assume that $w_m$ and $w_M$ ... or not. Reexamine the proof of Theorem to show that this difference in the definition does not affect the proof in any significant way.
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

18
views
peterlinz
decidability
theoryofcomputation
proof
0
votes
0
answers
8
Peter Linz Edition 5 Exercise 12.1 Question 1 (Page No. 307)
If the halting problem were decidable, then every recursively enumerable language would be recursive. Consequently, the halting problem is undecidable. Describe in detail how $H$ in given Theorem can be modified to produce $H^{\prime} $.
asked
Mar 14
in
Theory of Computation
by
Rishi yadav
Boss
(
11.2k
points)

19
views
peterlinz
decidability
theoryofcomputation
0
votes
0
answers
9
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
asked
Feb 28
in
Theory of Computation
by
srestha
Veteran
(
116k
points)

91
views
theoryofcomputation
reduction
decidability
0
votes
0
answers
10
#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?
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
259
points)

45
views
theoryofcomputation
finiteautomata
regularexpressions
decidability
+1
vote
0
answers
11
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?
asked
Jan 27
in
Theory of Computation
by
Abbas Ahmad
(
125
points)

47
views
decidability
selfdoubt
0
votes
0
answers
12
Ace Test Series: Theory Of Computation  Decidablity
asked
Jan 23
in
Theory of Computation
by
Shankar Kakde
(
195
points)

72
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
acetestseries
decidability
0
votes
1
answer
13
Turing Machines Theory
What is the difference between Turing Recognizable and Turing Decidable? Thanks!
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
83
points)

68
views
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
14
Reducible language ( Decidability)
asked
Jan 21
in
Theory of Computation
by
Na462
Loyal
(
6.8k
points)

68
views
theoryofcomputation
decidability
0
votes
3
answers
15
Gateforum mock 2
asked
Jan 20
in
Theory of Computation
by
Prince Sindhiya
Loyal
(
5.6k
points)

89
views
decidability
0
votes
0
answers
16
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.
asked
Jan 13
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
27.2k
points)

71
views
decidability
theoryofcomputation
0
votes
1
answer
17
Decidability
Let L be a DCFL and R is a regular language. Consider the below given problems. P : Is L ≠ R? Q : is R ⊂ L? Choose the correct option. Both problems P and Q are decidable. Both problems P and Q are undecidable. Problem Q is decidable and P is ... DCFL's, i.e when both languages are DCFL's. How do I analyze decidablity for different languages? In this case, for a RL and DCFL.
asked
Jan 9
in
Theory of Computation
by
utkarshkosta
(
29
points)

72
views
decidability
theoryofcomputation
0
votes
1
answer
18
toc(undecidability)
does intersection and complement problem of CSL language follow closure property? does intersection and complement problem of CSL language are decidable?
asked
Jan 9
in
Theory of Computation
by
harsh yadav
(
127
points)

36
views
decidability
0
votes
0
answers
19
© 2016 Pearson Education, Inc., Hoboken
What will be the bias used in a word addressing computer if the number of bits for exponent are 9? If 9 bits are used for the representation of a number, then what will be the maximum number in signed number range if the numbers are represented in 2’s complement?
asked
Jan 8
in
CO and Architecture
by
Mohamad Al Rebdawi
(
5
points)

31
views
computernetworks
theoryofcomputation
decidability
usermod
0
votes
0
answers
20
TOC(Undecidability)
L1 = { <M>  M halts on $\epsilon$ } L2 = { <M>  $\epsilon$ $\in$ L(M) } Which one is RE or not RE
asked
Jan 8
in
Theory of Computation
by
jatin khachane 1
Loyal
(
7.2k
points)

106
views
theoryofcomputation
decidability
+1
vote
0
answers
21
RE or non RE
CONSIDER THE FLLOWING LANGUAGE L={<M> M is a TM and L(M)=empty} Which of the following is true? a Decidable REC B Undecidable and RE cUndecidable and non RE d Decidable but RE
asked
Jan 8
in
Theory of Computation
by
bts1jimin
(
199
points)

108
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
22
MadeEasy Test Series: Theory Of Computation  Decidability
Among II and III. Which one is decidable ? Please explain in detail.
asked
Jan 4
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.4k
points)

67
views
madeeasytestseries
theoryofcomputation
decidability
+1
vote
0
answers
23
Decidability
Consider the following language over $\sum=\{0,1\}$ $L=\{<M>$ M is a turing machine that accepts all strings of length atmost 5 $\}$ Since, this is a nontrivial property of TM, so surely it is undecidable. Now, Applying Rice’s Theorem part 2, $T_{yes}=\{0,1\}$ and $T_{no}=\sum^*$ and $T_{yes} \subset T_{no}$ so this is NOT RE. Have I correctly applied property 2?
asked
Jan 3
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
27.2k
points)

91
views
decidability
theoryofcomputation
0
votes
0
answers
24
TOC Doubt
CFG G=(N,Σ,P,S) and a string x∈Σ∗, does x∈L(G)} ? Is it Decidable?
asked
Jan 2
in
Theory of Computation
by
Shamim Ahmed
Active
(
2.4k
points)

50
views
theoryofcomputation
decidability
0
votes
1
answer
25
Madeasy test series
Does equivalence of CFG decidable ? That is for two CFG G1 and G2 L(G1)= L(G2)? And if it is DCFG than is it decidable.
asked
Dec 30, 2018
in
Theory of Computation
by
Ayan21
(
79
points)

92
views
decidability
theoryofcomputation
contextfreelanguage
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
26
self doubt
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
asked
Dec 27, 2018
in
Theory of Computation
by
MRINMOY_HALDER
Active
(
2.8k
points)

58
views
theoryofcomputation
decidability
0
votes
0
answers
27
Decidability
So, this question is taken from here https://gateoverflow.in/151057/langleranglethereexistinputwhoselengththanwhichhalts%24 $L=\{<M> $M is a Turing machine and there exists an input whose length is less than 100 on which M halts$\}$ I got ... may take too long before it says yes, can we be sure whether we are really reaching an answer or TM has got into infinite loop?
asked
Dec 26, 2018
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
27.2k
points)

63
views
decidability
theoryofcomputation
+1
vote
1
answer
28
NTA NET DEC 18 Q36
asked
Dec 25, 2018
in
Theory of Computation
by
Sanjay Sharma
Boss
(
48.6k
points)

104
views
decidability
+1
vote
1
answer
29
NTA NET DEC 2018 Q21
asked
Dec 25, 2018
in
Theory of Computation
by
Sanjay Sharma
Boss
(
48.6k
points)

123
views
decidability
0
votes
0
answers
30
decidability
please someone explain what are these problems and how to solve these problems for every language with proper explanation? MEMBERSHIP PROBLEM EMPTINESS PROBLEM COMPLETENESS PROBLEM EQUILITY PROBLEM SUBSET PROBLEM DISJOINTNESS PROBLEM IS GIVEN LANGUAGE REGULAR FINITENESS PROBLEM
asked
Dec 24, 2018
in
Theory of Computation
by
Rahul_Rathod_
(
425
points)

83
views
decidability
#theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
Page:
« prev
1
2
3
4
5
6
7
8
9
...
14
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Minimal Deterministic Finite Automata
To be aware of fake GATE test series
Standard Book Exercise Questions for Computer Science
Follow @csegate
Recent questions tagged decidability
Recent Blog Comments
Favorite is not working for blogs.. In favorites...
Favourite option does work. But list options...
Blog favorite button doesnt work?
@Arjun Sir can we have an option to save such...
Thanks Sir
50,666
questions
56,167
answers
193,838
comments
94,008
users