search
Log In

Recent questions tagged turing-machine

0 votes
0 answers
5
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 be found on Mars someday} \end{matrix}\right.$ Is $A$ decidable? Why or why not? For the purposes 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, 2019 in Theory of Computation Lakshman Patel RJIT 14 views
0 votes
0 answers
6
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}.$
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 7 views
0 votes
0 answers
9
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.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 11 views
0 votes
0 answers
12
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. Each write operation (we'll call it a ... a special accept state at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 31 views
0 votes
0 answers
13
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 point, the machine can move its head ... the same position. Show that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 34 views
0 votes
0 answers
14
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\}$ If $\delta(q, a) = (r, b, RESET),$ when the machine ... not have the usual ability to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 126 views
0 votes
0 answers
15
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 that contains the input. Computation is defined as ... an end to the tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turing-recognizable languages.
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 22 views
0 votes
0 answers
16
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 machine model. (Hint: As a first step, consider the case whereby the Turing machine may alter each tape square at most twice. Use lots of tape.)
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 21 views
0 votes
0 answers
17
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}\}$
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 35 views
0 votes
0 answers
18
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}:$ Try all possible settings of $x_{1},\dots, x_{k}$ to integer values. Evaluate $p$ on all of these settings. If any of these settings evaluates to $0$, accept; otherwise, reject.$”$
asked Oct 15, 2019 in Theory of Computation Lakshman Patel RJIT 37 views
0 votes
0 answers
19
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 same as the input alphabet $\Sigma$? Can a Turing machine’s head ever be in the same location in two successive steps? Can a Turing machine contain just a single state?
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 41 views
0 votes
1 answer
20
0 votes
0 answers
21
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 tree has finitely many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
asked Oct 13, 2019 in Theory of Computation Lakshman Patel RJIT 41 views
0 votes
0 answers
22
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, 2019 in Theory of Computation Lakshman Patel RJIT 11 views
0 votes
0 answers
23
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, 2019 in Theory of Computation Lakshman Patel RJIT 13 views
0 votes
0 answers
24
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$ ... by one move of $M$. If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 88 views
0 votes
0 answers
25
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE. 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 no 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, 2019 in Theory of Computation Lakshman Patel RJIT 46 views
0 votes
0 answers
26
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$. The set of triples $(M_{1},M_{2},M_{3})$ such that $L(M_{1}) = L(M_{2})L(M_{3})$ ; i.e., the language of the first is the concatenation of the languages of the two $TM's$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 32 views
0 votes
0 answers
27
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$ ... . The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, never scans any tape cell more than once.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 31 views
0 votes
0 answers
29
0 votes
0 answers
30
The Big Computer Corp. has decided to bolster its sagging market share by manufacturing a high-tech version of the Turing machine called, $BWTM$ that is equipped with bells and whistles. The $BWTM$ is basically the same as your ordinary Turing machine, except that each state of ... just entered. Prove that it is undecidable whether a given $BWTM \ M$, on given input $w$, ever blows the whistle.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 32 views
...