search
Log In

Recent questions tagged turing-machine

2 votes
3 answers
1
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
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 3.1k views
0 votes
4 answers
2
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
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 1.6k views
2 votes
3 answers
3
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 661 views
0 votes
3 answers
4
Which of the following pairs have different expressive power? Single-tape-turing machine and multi-dimensional turing machine. Multi-tape turing machine and multi-dimensional turing machine. Deterministic push down automata and non-deterministic pushdown automata. Deterministic finite automata and Non-deterministic finite automata
asked Mar 24, 2020 in Theory of Computation jothee 343 views
0 votes
1 answer
5
0 votes
0 answers
6
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}\}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 178 views
0 votes
0 answers
7
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 obtain a sequence, $x, f(x), f(f(x)), \dots$ ... problem. Suppose that $ATM$ were 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 Lakshman Patel RJIT 118 views
1 vote
0 answers
8
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 Lakshman Patel RJIT 170 views
0 votes
0 answers
9
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 consisting of Turing ... any $TMs$. Prove 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 Lakshman Patel RJIT 87 views
0 votes
0 answers
10
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$ ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 182 views
1 vote
0 answers
11
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 the rectangle contain the symbol $\#$ and the internal squares contain ... . Consider the problem 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 Lakshman Patel RJIT 232 views
0 votes
0 answers
12
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 of a $2DFA$ is finite and is just large ... $E_{2DFA}$ is not decidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 143 views
0 votes
0 answers
15
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 started with a blank tape. Let $BB(k)$ be the 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 Lakshman Patel RJIT 142 views
1 vote
0 answers
16
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 Lakshman Patel RJIT 291 views
0 votes
0 answers
17
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.
asked Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 84 views
0 votes
0 answers
18
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 Lakshman Patel RJIT 91 views
0 votes
0 answers
19
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.
asked Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 101 views
0 votes
0 answers
20
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.
asked Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 98 views
1 vote
0 answers
21
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.
asked Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 60 views
0 votes
0 answers
23
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.
asked Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 147 views
0 votes
0 answers
25
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 Lakshman Patel RJIT 33 views
0 votes
0 answers
26
0 votes
0 answers
27
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 decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
asked Oct 17, 2019 in Theory of Computation Lakshman Patel RJIT 102 views
...