Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Turing Machine Notes
Recent questions tagged turing-machine
0
votes
1
answer
31
Test Series gate@Zeal 2022
Please explain the ans. Ans is (B)
Please explain the ans. Ans is (B)
SKMAKM
352
views
SKMAKM
asked
Jul 19, 2022
Theory of Computation
turing-machine
+
–
2
votes
1
answer
32
GO Classes Test Series 2023 | Theory of Computation | Test 3 | Question: 5
The language $\left\{w w \mid w \in(0+1)^{\ast}\right\}$ is not accepted by any Turing machine accepted by some Turing machine, but by no pushdown automaton accepted by some pushdown automaton, but not context-free context-free, but not regular
The language $\left\{w w \mid w \in(0+1)^{\ast}\right\}$ isnot accepted by any Turing machineaccepted by some Turing machine, but by no pushdown automatonaccepted by some...
GO Classes
293
views
GO Classes
asked
Jun 27, 2022
Theory of Computation
goclasses2024-toc-3-weekly-quiz
goclasses
theory-of-computation
pushdown-automata
turing-machine
1-mark
+
–
12
votes
2
answers
33
GATE CSE 2022 | Question: 36
Which of the following is/are undecidable? Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$ Given a Turing machine $\textit{M},$ decide if $\textit{L(M)}$ is ... $\textit{M},$ decide if $\textit{M}$ takes more than $1073$ steps on every string.
Which of the following is/are undecidable?Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$Given a Turin...
Arjun
10.1k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
turing-machine
decidability
multiple-selects
2-marks
+
–
0
votes
1
answer
34
Automata
L = {w: w ε{0,1}*,Every substring of four symbols has at most two 0’s} Write a program using c++ or java. The input program is the string to be tested.The automata must be tested with v= {w: w ε L} and the output should either reject or accept the string v.
L = {w: w ε{0,1}*,Every substring of four symbols has at most two 0’s}Write a program using c++ or java.The input program is the string to be tested.The automata must ...
fxavain
331
views
fxavain
asked
Feb 11, 2022
Compilers, Architecture, HPC
finite-automata
theory-of-computation
turing-machine
+
–
2
votes
2
answers
35
Made Easy Test series
Consider the following language : P1 : {<M, x, k>| M is a TM and M does not halt on x within k steps} P2 : {<M>| M is TM and L(M) = $\phi$} P3 : {<M>| M is a TM and L(M) = finite language} The number of problems which are not RE is/are _______ ?
Consider the following language :P1 : {<M, x, k>| M is a TM and M does not halt on x within k steps}P2 : {<M>| M is TM and L(M) = $\phi$}P3 : {<M>| M is a TM and L(M) = f...
Aashay kaurav
657
views
Aashay kaurav
asked
Oct 16, 2021
Theory of Computation
made-easy-test-series
theory-of-computation
turing-machine
+
–
1
votes
1
answer
36
GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 30
The language accepted by a Turing Machine if its Read/Write head is converted to a Read Only one is? Recursive but not necessarily context-free Deterministic context-free but not necessarily regular Regular None of the above
The language accepted by a Turing Machine if its Read/Write head is converted to a Read Only one is?Recursive but not necessarily context-freeDeterministic context-free b...
gatecse
136
views
gatecse
asked
Oct 15, 2020
Theory of Computation
go2025-mix-3
identify-class-language
turing-machine
+
–
2
votes
3
answers
37
NIELIT 2016 DEC Scientist B (CS) - Section B: 6
Which of the following is wrong? Turing machine is a simple mathematical model of general purpose computer Turing machine is more powerful than finite automata Turing Machine can be simulated by a general purpose computer All of these
Which of the following is wrong?Turing machine is a simple mathematical model of general purpose computerTuring machine is more powerful than finite automataTuring Machin...
admin
9.6k
views
admin
asked
Mar 31, 2020
Theory of Computation
nielit2016dec-scientistb-cs
theory-of-computation
turing-machine
+
–
1
votes
4
answers
38
NIELIT 2017 DEC Scientist B - Section B: 37
Which of the following statement is true? $S1$: The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine. $S2$: Every non-deterministic Turing machine has an equivalent deterministic Turing machine. $S1$ $S2$ Both $S1$ and $S2$ None of the options
Which of the following statement is true?$S1$: The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine.$S2$: Every non-determin...
admin
3.1k
views
admin
asked
Mar 30, 2020
Theory of Computation
nielit2017dec-scientistb
theory-of-computation
turing-machine
+
–
2
votes
2
answers
39
NIELIT 2017 DEC Scientist B - Section B: 57
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options
Which machine is equally powerful in both deterministic and non-deterministic form?Push Down AutomataTuring machineLinear Bounded AutomataNone of the options
admin
1.7k
views
admin
asked
Mar 30, 2020
Theory of Computation
nielit2017dec-scientistb
pushdown-automata
turing-machine
+
–
0
votes
1
answer
40
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$Is $X$ decidable? Prove you...
admin
724
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
41
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\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
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\}$.$PREF...
admin
455
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
turing-machine
decidability
proof
+
–
0
votes
0
answers
42
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.
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 inte...
admin
362
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
1
votes
0
answers
43
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} \}$.
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 lan...
admin
395
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
+
–
0
votes
0
answers
44
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.
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 languag...
admin
459
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
+
–
0
votes
0
answers
45
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.
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 languag...
admin
411
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
rice-theorem
proof
+
–
1
votes
0
answers
46
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A two-dimensional finite automaton $(2DIM-DFA)$ 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.
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$. The squares along the boundary of th...
admin
469
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
+
–
0
votes
0
answers
47
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the in...
admin
397
views
admin
asked
Oct 20, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
turing-machine
decidability
proof
+
–
0
votes
0
answers
48
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}$.
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
admin
301
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
reduction
proof
+
–
0
votes
0
answers
49
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 Turing-recognizable.
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 Tur...
admin
211
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
+
–
0
votes
0
answers
50
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.
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$,...
admin
418
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
computability
proof
+
–
1
votes
0
answers
51
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.
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 t...
admin
1.0k
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
52
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 left-most tape cell. Formulate this problem as a language and show that it is undecidable.
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 left-most tape cell. Formulat...
admin
301
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
53
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.
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....
admin
340
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
54
Michael Sipser Edition 3 Exercise 5 Question 12 (Page No. 239)
Consider the problem of determining whether a single-tape 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.
Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any inp...
admin
400
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
55
Michael Sipser Edition 3 Exercise 5 Question 11 (Page No. 239)
Consider the problem of determining whether a two-tape 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.
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input s...
admin
282
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
1
votes
0
answers
56
Michael Sipser Edition 3 Exercise 5 Question 10 (Page No. 239)
Consider the problem of determining whether a two-tape 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.
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem...
admin
251
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
57
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.
Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.
admin
214
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
decidability
proof
+
–
0
votes
0
answers
58
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 left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the $PCP$ construction to handle this case.
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make...
admin
314
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
post-correspondence-problem
proof
+
–
0
votes
0
answers
59
Michael Sipser Edition 3 Exercise 5 Question 6 (Page No. 239)
Show that $\leq_{m}$ is a transitive relation.
Show that $\leq_{m}$ is a transitive relation.
admin
169
views
admin
asked
Oct 19, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
reduction
proof
+
–
Page:
« prev
1
2
3
4
5
6
7
...
17
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
