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 turingmachine
Turing Machine Notes
0
votes
0
answers
1
Michael Sipser Edition 3 Exercise 4 Question 4 (Page No. 211)
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
asked
Oct 16
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

14
views
michaelsipser
theoryofcomputation
turingmachine
cfg
decidability
proof
0
votes
0
answers
2
Michael Sipser Edition 3 Exercise 4 Question 3 (Page No. 211)
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
asked
Oct 16
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
michaelsipser
theoryofcomputation
turingmachine
finiteautomata
decidability
proof
0
votes
0
answers
3
Michael Sipser Edition 3 Exercise 4 Question 1 (Page No. 210)
asked
Oct 16
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
descriptive
0
votes
0
answers
4
Michael Sipser Edition 3 Exercise 3 Question 22 (Page No. 190)
Let $A$ be the language containing only the single string $s$ ... of this problem, assume that the question of whether life will be found on Mars has an unambiguous $YES$ or $NO$ answer.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

1
view
michaelsipser
theoryofcomputation
turingmachine
decidability
descriptive
0
votes
0
answers
5
Michael Sipser Edition 3 Exercise 3 Question 21 (Page No. 190)
Let $c_{1}x^{n} + c_{2}x^{n1} + \dots + c_{n}x + c_{n+1}$ be a polynomial with a root at $x = x_{0}.$ Let $c_{max}$ be the largest absolute value of a $c_{i}.$ Show that $\mid x_{0} \mid < (n+1)\frac{c_{max}}{\mid c_{1} \mid}.$
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

1
view
michaelsipser
theoryofcomputation
turingmachine
polynomials
proof
0
votes
0
answers
6
Michael Sipser Edition 3 Exercise 3 Question 20 (Page No. 190)
Show that singletape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

2
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
7
Michael Sipser Edition 3 Exercise 3 Question 19 (Page No. 190)
Show that every infinite Turingrecognizable language has an infinite decidable subset.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
8
Michael Sipser Edition 3 Exercise 3 Question 17 (Page No. 189)
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turingrecognizable language consisting of $TM$ descriptions. Show that there is a decidable language $C$ consisting of $TM$ descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
9
Michael Sipser Edition 3 Exercise 3 Question 16 (Page No. 189)
Show that the collection of Turingrecognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
0
votes
0
answers
10
Michael Sipser Edition 3 Exercise 3 Question 15 (Page No. 189)
Show that the collection of decidable languages is closed under the operation of union. concatenation. star. complementation. intersection.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
11
Michael Sipser Edition 3 Exercise 3 Question 14 (Page No. 189)
A queue automaton is like a pushdown automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the lefthand end and read only at the righthand end. ... at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turingrecognizable.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
12
Michael Sipser Edition 3 Exercise 3 Question 13 (Page No. 189)
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,S\}$ At each ... that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
13
Michael Sipser Edition 3 Exercise 3 Question 12 (Page No. 189)
A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,RESET\}$ ... to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turingrecognizable languages.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
14
Michael Sipser Edition 3 Exercise 3 Question 11 (Page No. 189)
A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion ... tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turingrecognizable languages.
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

2
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
descriptive
0
votes
0
answers
15
Michael Sipser Edition 3 Exercise 3 Question 10 (Page No. 188)
Say that a writeonce Turing machine is a singletape TM that can alter each tape square at most once (including the input portion of the tape). Show that this variant Turing machine model is equivalent to the ordinary Turing ... , consider the case whereby the Turing machine may alter each tape square at most twice. Use lots of tape.)
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
michaelsipser
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 3 Question 8 (Page No. 188)
Give implementationlevel descriptions of Turing machines that decide the following languages over the alphabet $\{0,1\}$. $\{w \mid w \text{contains an equal number of 0s and 1s}\}$ $\{w \mid w \text{contains twice as many 0s as 1s}\}$ $\{w \mid w \text{does not contain twice as many 0s as 1s}\}$
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 3 Question 7 (Page No. 188)
Explain why the following is not a description of a legitimate Turing machine. $M_{bad} = $ On input $\langle p \rangle,$ a polynomial over variables $x_{1},\dots,x_{k}:$ ... . Evaluate $p$ on all of these settings. If any of these settings evaluates to $0$, accept; otherwise, reject.$ $
asked
Oct 15
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
michaelsipser
theoryofcomputation
turingmachine
legitimateturingmachine
descriptive
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 3 Question 5 (Page No. 188)
Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning. Can a Turing machine ever write the blank symbol $\sqcup$ on its tape? Can the tape alphabet $\Gamma$ be the ... head ever be in the same location in two successive steps? Can a Turing machine contain just a single state?
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

13
views
michaelsipser
theoryofcomputation
turingmachine
descriptive
0
votes
1
answer
19
Michael Sipser Edition 3 Exercise 3 Question 4 (Page No. 187)
Give a formal definition of an enumerator. Consider it to be a type of twotape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

9
views
michaelsipser
theoryofcomputation
turingmachine
enumeratedlanguage
descriptive
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 3 Question 3 (Page No. 187)
Modify the proof of Theorem $3.16$ to obtain Corollary $3.19$, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a ... many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
michaelsipser
theoryofcomputation
nondeterminism
turingmachine
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 3 Question 2 (Page No. 187)
This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ enters when started on the indicated input string. $11$ $1\#1$ $1\#\#1$ $10\#11$ $10\#10$
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

3
views
michaelsipser
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 3 Question 1 (Page No. 187)
This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ enters when started on the indicated input string. $0$ $00$ $000$ $000000$
asked
Oct 13
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

2
views
michaelsipser
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
23
Ullman (TOC) Edition 3 Exercise 9.4 Question 4 (Page No. 412)
A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\Sigma$, we say that $wy\vdash yx$. That is ... . If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

64
views
ullman
theoryofcomputation
turingmachine
undecidable
descriptive
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 9.3 Question 8 (Page No. 401)
Tell whether each of the following are recursive, REbutnotrecursive, or nonRE. The set of all $TM$ codes for $TM's$ that halt on every input. The set of all $TM$ codes for $TM's$ ... that halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

18
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 9.3 Question 7 (Page No. 400  401)
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ such that $L(M_{1}\cap L_(M_{2})=\phi$. ... $TM's$.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

12
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 9.3 Question 6 (Page No. 400)
Show that the following questions are decidable: The set of codes for $TM's \ M$ such that when started with blank tape will eventually write some nonblank symbol on its tape. Hint: If $M$ has $m$ states, consider the first $m$ transitions ... $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

18
views
ullman
theoryofcomputation
turingmachine
decidability
descriptive
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 9.3 Question 5 (Page No. 400)
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

11
views
ullman
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
descriptive
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 9.3 Question 3 (Page No. 400)
Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

5
views
ullman
theoryofcomputation
turingmachine
undecidable
descriptive
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 9.3 Question 2 (Page No. 400)
The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a hightech version of the Turing machine called, $BWTM$ that is equipped with bells and whistles. The $BWTM$ is basically the same as your ordinary ... that it is undecidable whether a given $BWTM \ M$, on given input $w$, ever blows the whistle.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 9.3 Question 1 (Page No. 400)
Show that the set of Turingmachine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.
asked
Jul 21
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

20
views
ullman
theoryofcomputation
turingmachine
undecidable
descriptive
Page:
« prev
1
2
3
4
5
6
7
...
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
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
Not really. It was excluding shipping I guess....
Ok sir. Actually pricing on Flipkart is 200 less...
NO.
Is this application open for 2020 graduates i.e....
@Ayush Upadhyaya sir any approximate idea...
50,645
questions
56,597
answers
195,837
comments
102,127
users