The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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 turingmachine
Turing Machine Notes
0
votes
1
answer
1
UGCNETJan2017III: 62
Which of the following pairs have different expressive power? Singletapeturing machine and multidimensional turing machine. Multitape turing machine and multidimensional turing machine. Deterministic push down automata and nondeterministic pushdown automata. Deterministic finite automata and Nondeterministic finite automata
asked
Mar 24
in
Theory of Computation
by
jothee

57
views
ugcnetjan2017iii
theoryofcomputation
turingmachine
0
votes
1
answer
2
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a singletape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

125
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIXFREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefixfree}\}$.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

56
views
michaelsipser
theoryofcomputation
contextfreegrammars
turingmachine
decidability
proof
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you ... decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

47
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
+1
vote
0
answers
5
Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

46
views
michaelsipser
theoryofcomputation
turingmachine
decidability
ricetheorem
proof
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

29
views
michaelsipser
theoryofcomputation
turingmachine
decidability
ricetheorem
proof
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

40
views
michaelsipser
theoryofcomputation
turingmachine
decidability
ricetheorem
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A twodimensional finite automaton $(2DIMDFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$ ... of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

88
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a twoheaded finite automaton $(2DFA)$ to be a deterministic finite automaton that has two readonly, bidirectional heads that start at the lefthand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

29
views
michaelsipser
theoryofcomputation
turingmachine
decidability
reduction
proof
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turingrecognizable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

18
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 5 Question 16 (Page No. 240)
Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$, consider all $k$state TMs that halt when ... maximum number of $1s$ that remain on the tape among all of these machines. Show that $BB$ is not a computable function.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

35
views
michaelsipser
theoryofcomputation
turingmachine
computability
proof
+1
vote
0
answers
13
Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

95
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the leftmost tape cell. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

20
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 5 Question 13 (Page No. 239)
A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

27
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 5 Question 12 (Page No. 239)
Consider the problem of determining whether a singletape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

43
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 5 Question 11 (Page No. 239)
Consider the problem of determining whether a twotape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

27
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 5 Question 10 (Page No. 239)
Consider the problem of determining whether a twotape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem as a language and show that it is undecidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

15
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 5 Question 9 (Page No. 239)
Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

23
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 5 Question 8 (Page No. 239)
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the lefthand end of the tape. Suppose that we did not make this modification to $M$. Modify the $PCP$ construction to handle this case.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

33
views
michaelsipser
theoryofcomputation
turingmachine
postcorrespondingproblem
proof
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 5 Question 6 (Page No. 239)
Show that $\leq_{m}$ is a transitive relation.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

9
views
michaelsipser
theoryofcomputation
turingmachine
reduction
proof
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 5 Question 5 (Page No. 239)
Show that $A_{TM}$ is not mapping reducible to $E_{TM}$. In other words, show that no computable function reduces $A_{TM}$ to $E_{TM}$. (Hint: Use a proof by contradiction, and facts you already know about $A_{TM}$ and $E_{TM}$.)
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

9
views
michaelsipser
theoryofcomputation
turingmachine
reduction
proof
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 5 Question 3 (Page No. 239)
Find a match in the following instance of the Post Correspondence Problem. $\begin{Bmatrix} \bigg[\dfrac{ab}{abab}\bigg],&\bigg[\dfrac{b}{a}\bigg],&\bigg[\dfrac{aba}{b}\bigg], & \bigg[\dfrac{aa}{a}\bigg] \end{Bmatrix}$
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

19
views
michaelsipser
theoryofcomputation
turingmachine
postcorrespondenceproblem
proof
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 4 Question 30 (Page No. 212)
Let $A$ be a Turingrecognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not ... $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
asked
Oct 18, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

22
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
decidability
proof
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 4 Question 11 (Page No. 211)
Let $INFINITE_{PDA} = \{\langle{ M \rangle} \mid \text{M is a PDA and L(M) is an infinite language}\}$. Show that $INFINITE_{PDA}$ is decidable.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

12
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 4 Question 10 (Page No. 211)
Let $INFINITE_{DFA} = \{\langle{ A \rangle} \mid \text{ A is a DFA and L(A) is an infinite language}\}$. Show that $INFINITE_{DFA}$ is decidable.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

11
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 4 Question 9 (Page No. 211)
Review the way that we define sets to be the same size in Definition $4.12$ (page $203$). Show that “is the same size” is an equivalence relation.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

28
views
michaelsipser
theoryofcomputation
turingmachine
countableuncountableset
proof
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 4 Question 8 (Page No. 211)
Let $T = \{(i, j, k)\mid i, j, k \in N \}$. Show that $T$ is countable.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

21
views
michaelsipser
theoryofcomputation
turingmachine
countableuncountableset
proof
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 4 Question 7 (Page No. 211)
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

14
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 4 Question 6 (Page No. 211)
Let $X$ be the set $\{1, 2, 3, 4, 5\}$ and $Y$ be the set $\{6, 7, 8, 9, 10\}$. We describe the functions $f : X\rightarrow Y$ and $g : X\rightarrow Y$ in the following tables. Answer each part and give a reason for each ... $f$ onetoone? Is $f$ onto? Is $f$ a correspondence? Is $g$ onetoone? Is $g$ onto? Is $g$ a correspondence?
asked
Oct 17, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

18
views
michaelsipser
theoryofcomputation
turingmachine
proof
Page:
1
2
3
4
5
6
...
16
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged turingmachine
Recent Blog Comments
Q1. I don't know any trick or method, I usually...
Yeah, Now it's on.
Can you check now?
Even I filled NIELIT form which had similar...
Today's test will be late  either midnight or...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,580
answers
201,986
comments
95,396
users