Problems

Let $T=\left\{ \langle M\rangle \mid M \text{ is a TM that accepts } w^{\mathcal{R}} \text{ whenever it accepts } w\right\}$. Show that $T$ 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 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 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 input string. 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. 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. 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 at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.

Let $\Gamma =\left\{ 0,1, \sqcup \right\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $\operatorname {BB}: \mathcal{N} \longrightarrow \mathcal{N}$ as follows. For each value of $k$, consider all $k$-state TMs that halt when started with a blank tape. Let $\operatorname {BB}(k)$ be the maximum number of 1s that remain on the tape among all of these machines. Show that $\operatorname {BB}$ is not a computable function.

Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma =\left\{ 1\right\}$.

Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma =\left\{ 0,1\right\}$.

In the silly Post Correspondence Problem, SPCP, the top string in each pair has the same length as the bottom string. Show that the SPCP is decidable.

Prove that there exists an undecidable subset of 1*.

Let $\operatorname {AMBIG}_{\mathrm{CFG}}=\left\{ \langle G\rangle \mid G\text{ is an ambiguous CFG }\right\}$. Show that $\operatorname {AMBIG}_{\mathrm{CFG}}$ is undecidable. (Hint: Use a reduction from $\operatorname {PCP}$. Given an instance

of the Post Correspondence Problem, construct a $\mathrm{CFG} G$ with the rules

where $\mathrm{a}_{1}, \ldots , \mathrm{a}_{k}$ are new terminal symbols. Prove that this reduction works.)

Show that $A$ is Turing-recognizable iff $A \leq_{\mathrm{m}} A_{\text{TM }}$.

Show that $A$ is decidable iff $A \leq_{\mathrm{m}} 0^{*} 1^{*}$.

Let $J=\left\{ w \mid \text{either } w=0 x \text{ for some } x \in A_{\text{TM }}, \text{ or } w=1 y \text{ for some } y \in \overline{A_{\text{TM }}}\right\}$. Show that neither $J$ nor $\bar{J}$ is Turing-recognizable.

Give an example of an undecidable language $B$, where $B \leq_{\mathrm{m}} \bar{B}$.

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 enough to contain the input plus two additional blank tape cells, one on the left-hand end and one on the right-hand end, that serve as delimiters. A 2DFA accepts its input by entering a special accept state. For example, a 2DFA can recognize the language $\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mathrm{c}^{n} \mid n \geq 0\right\}$.

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 symbols over the input alphabet $\Sigma$. The transition function $\delta : Q \times (\Sigma \cup \left\{ \# \right\} ) \longrightarrow Q \times \left\{ \mathrm{L}, \mathrm{R}, \mathrm{U}, \mathrm{D}\right\}$ indicates the next state and the new head position (Left, Right, Up, Down). The machine accepts when it enters one of the designated accept states. It rejects if it tries to move off the input rectangle or if it never halts. Two such machines are equivalent if they accept the same rectangles. Consider the problem of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it 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 language has property $P$ is undecidable.

In more formal terms, let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language-whenever $L\left(M_{1}\right)=L\left(M_{2}\right)$, we have $\left\langle M_{1}\right\rangle \in P$ iff $\left\langle M_{2}\right\rangle \in P$. Here, $M_{1}$ and $M_{2}$ are any TMs. Prove that $P$ is an undecidable language.

Show that both conditions in Problem 5.28 are necessary for proving that $P$ is undecidable.

Problem 5.28 (Rice's theorem): Let $P$ be a language consisting of Turing machine descriptions where $P$ fulfills two conditions. First, $P$ is nontrivial-it contains some, but not all, TM descriptions. Second, $P$ is a property of the TM's language-whenever $L\left(M_{1}\right)=L\left(M_{2}\right)$, we have $\left\langle M_{1}\right\rangle \in P$ iff $\left\langle M_{2}\right\rangle \in P$. Here, $M_{1}$ and $M_{2}$ are any TMs.

Use Rice's theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages.

Let

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)), \ldots$. Stop if you ever hit 1. For example, if $x=17$, you get the sequence 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Extensive computer tests have shown that every starting point between 1 and a large positive integer gives a sequence that ends in 1. But the question of whether all positive starting points end up at 1 is unsolved; it is called the $3 x+1$ problem. Suppose that $A_{\text{TM }}$ were decidable by a TM $H$. Use $H$ to describe a TM that is guaranteed to state the answer to the $3 x+1$ problem.

Prove that the following two languages are undecidable.

Consider the problem of determining whether a PDA accepts some string of the form $\left\{ w w \mid w \in \left\{ 0,1\right\}^{*}\right\}$. Use the computation history method to show that this problem is undecidable.

Let $X=\left\{ \langle M, w\rangle \mid M\text{ is a single-tape TM that never modifies the portion of the tape that contains the input }w\right\}$. Is $X$ decidable? Prove your answer.

Say that a variable $A$ in CFG $G$ is necessary if it appears in every derivation of some string $w \in G$. Let $\operatorname {NECESSARY}_{\mathrm{CFG}}=\left\{ \langle G, A\rangle \mid A\text{ is a necessary variable in }G\right\}$.

• Say that a CFG is minimal if none of its rules can be removed without changing the language generated. Let $\operatorname {MIN}_{\mathrm{CFG}}=\left\{ \langle G\rangle \mid G\text{ is a minimal CFG }\right\}$.