Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Turing Machine Notes
Recent questions tagged turing-machine
0
votes
0
answers
61
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}$
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}\bi...
admin
242
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
post-correspondence-problem
proof
+
–
0
votes
0
answers
62
Michael Sipser Edition 3 Exercise 4 Question 30 (Page No. 212)
Let $A$ be a Turing-recognizable 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$.)
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a ...
admin
306
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
decidability
proof
+
–
0
votes
0
answers
63
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.
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.
admin
163
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
64
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.
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.
admin
179
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
65
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.
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.
admin
414
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
countable-uncountable-set
proof
+
–
0
votes
0
answers
66
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.
Let $T = \{(i, j, k)\mid i, j, k \in N \}$. Show that $T$ is countable.
admin
477
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
countable-uncountable-set
proof
+
–
0
votes
0
answers
67
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.
Let $B$ be the set of all infinite sequences over $\{0,1\}$. Show that $B$ is uncountable using a proof by diagonalization.
admin
141
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
68
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$ one-to-one? Is $f$ onto? Is $f$ a correspondence? Is $g$ one-to-one? Is $g$ onto? Is $g$ a correspondence?
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 t...
admin
149
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
proof
+
–
0
votes
0
answers
69
Michael Sipser Edition 3 Exercise 4 Question 5 (Page No. 211)
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.
admin
131
views
admin
asked
Oct 17, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
+
–
0
votes
0
answers
70
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.
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
admin
187
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
context-free-grammar
decidability
proof
+
–
0
votes
0
answers
71
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.
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
admin
210
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
finite-automata
decidability
proof
+
–
0
votes
0
answers
72
Michael Sipser Edition 3 Exercise 4 Question 1 (Page No. 210)
admin
500
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
turing-machine
descriptive
+
–
0
votes
0
answers
73
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.
Let $A$ be the language containing only the single string $s$, where$s = \left\{\begin{matrix} \text{0 if life never will be found on Mars} \\ \:\: \text{1 if life will b...
admin
202
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
descriptive
+
–
0
votes
0
answers
74
Michael Sipser Edition 3 Exercise 3 Question 21 (Page No. 190)
Let $c_{1}x^{n} + c_{2}x^{n-1} + \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}.$
Let $c_{1}x^{n} + c_{2}x^{n-1} + \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 tha...
admin
154
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
polynomials
proof
+
–
0
votes
0
answers
75
Michael Sipser Edition 3 Exercise 3 Question 20 (Page No. 190)
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
admin
152
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
+
–
0
votes
0
answers
76
Michael Sipser Edition 3 Exercise 3 Question 19 (Page No. 190)
Show that every infinite Turing-recognizable language has an infinite decidable subset.
Show that every infinite Turing-recognizable language has an infinite decidable subset.
admin
186
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
+
–
0
votes
0
answers
77
Michael Sipser Edition 3 Exercise 3 Question 17 (Page No. 189)
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable 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.
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable la...
admin
123
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
descriptive
+
–
0
votes
0
answers
78
Michael Sipser Edition 3 Exercise 3 Question 16 (Page No. 189)
Show that the collection of Turing-recognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.
Show that the collection of Turing-recognizable languages is closed under the operation ofunion.concatenation.star.intersection.homomorphism.
admin
150
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
79
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.
Show that the collection of decidable languages is closed under the operation ofunion.concatenation.star.complementation.intersection.
admin
124
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
+
–
0
votes
0
answers
80
Michael Sipser Edition 3 Exercise 3 Question 14 (Page No. 189)
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. ... at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end a...
admin
337
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
descriptive
+
–
0
votes
0
answers
81
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?
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\ti...
admin
195
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
descriptive
+
–
0
votes
0
answers
82
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 Turing-recognizable languages.
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 \ti...
admin
474
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
descriptive
+
–
0
votes
0
answers
83
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 Turing-recognizable languages.
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 f...
admin
225
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
descriptive
+
–
0
votes
0
answers
84
Michael Sipser Edition 3 Exercise 3 Question 10 (Page No. 188)
Say that a write-once Turing machine is a single-tape 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.)
Say that a write-once Turing machine is a single-tape TM that can alter each tape square at most once (including the input portion of the tape). Show that this variant Tu...
admin
360
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
85
Michael Sipser Edition 3 Exercise 3 Question 8 (Page No. 188)
Give implementation-level 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}\}$
Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet $\{0,1\}$. $\{w \mid w \text{contains an equal number of...
admin
377
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
86
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.$ $
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}...
admin
377
views
admin
asked
Oct 15, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
legitimate-turing-machine
descriptive
+
–
0
votes
0
answers
87
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?
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$ ...
admin
384
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
descriptive
+
–
0
votes
1
answer
88
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 two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.
Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enume...
admin
587
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
enumerated-language
descriptive
+
–
0
votes
0
answers
89
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.)
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 t...
admin
466
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
non-determinism
turing-machine
descriptive
+
–
0
votes
0
answers
90
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$
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}$ ...
admin
170
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
descriptive
+
–
Page:
« prev
1
2
3
4
5
6
7
8
...
17
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register