Recent questions tagged turing-machine

1
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.
2
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.
3
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.
4
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.
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}.$
7
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.
8
Show that every infinite Turing-recognizable language has an infinite decidable subset.
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.
10
Show that the collection of Turing-recognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.
11
Show that the collection of decidable languages is closed under the operation of union. concatenation. star. complementation. intersection.
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.
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?
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.
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.
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.)
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}\}$
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.$”$
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?
20
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.
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.)
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$
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$
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$.
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.
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$.
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.
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.
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.
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.