Undecidable Problems

Given a DTM M and a string $y$, determine whether $M$ halts on some input $z$ which is greater than or equal to $y$.

Given two DTM's $M_{x}$ and $M_{y}$, determine whether they are equivalent (i.e., whether they compute the same function).

Given a DTM $M$, an input $y$ and a state $q_{i}$ of $M$, determine whether $M$ ever enters state $q_{i}$ in the computation on input $y$.

Given a DTM M, determine whether the computation of M(111) contains a configuration in which the tape contains a substring 000.

Given a grammar $G$ and a string $x$, determine whether $x \in L(G)$.

Given a grammar $G$ and two strings $x$ and $y$, determine whether $x \xrightarrow [G]{*} y$.

Given a grammar $G$ and two strings $x, y \in L(G)$, determine whether there is a derivation of $x$ that is longer than the shortest derivation of $y$. (The length of a derivation is the number of sentential forms in the derivation.)

Given a grammar $G$, determine whether $L(G)=\emptyset$.

Given two grammars $G_{1}$ and $G_{2}$, determine whether $L\left(G_{1}\right) \subseteq L\left(G_{2}\right)$.

Given a grammar $G$, determine whether $L(G)$ is a context-free language (i.e, for a given unrestricted grammar $G$, determine whether there is an equivalent context-free grammar).

Given a one-way, one-tape DTM $M$ (defined in Section 4.1) and a string $x$, determine whether the tape head of $M$ will ever visit the $(2 n)$ th cell in the computation of $M$ on input $x$, where $n=\left|x\right|$ (we call the leftmost cell of the tape the 0th cell, and the one to its right the first cell, etc.).

Given a two-way, one-tape DTM $M$ (defined in Section 4.3) and a string $x$, determine whether the tape head of $M$ will ever visit the $(2 n)$ th cell in the computation of $M$ on input $x$, where $n=\left|x\right|$ (we call the cell holding the leftmost symbol of $x$ the first cell, and the cell to its right the second cell, etc.).

Given a two-way, one-tape DTM $M$ and a string $x$, determine whether the tape head of $M$ will move left for more than $n$ times (not necessarily in consecutive moves) in the computation of $M$ on input $x$, where $n=\left|x\right|$.

Given a two-way, one-tape DTM $M$ whose tape symbol set is $\Gamma =\left\{ a, b, \mathrm{~ B}\right\}$ and a string $x \in \left\{ a, b\right\}^{*}$, determine whether $M$ will ever overwrite a symbol $a$ by a symbol $b$ in its computation on input $x$.

Given two DTM's $M_{1}$ and $M_{2}$ and two strings $x_{1}$ and $x_{2}$, determine whether it is true that sometime during the computation of $M_{1}$ on input $x_{1}$ and the computation of $M_{2}$ on input $x_{2}$, the first three cells of their tapes contain the same symbols (i.e., whether there is a configuration $\alpha$ of the computation of $M_{1}\left(x_{1}\right)$ and a configuration $\beta$ of the computation of $M_{2}\left(x_{2}\right)$ such that the first three tape symbols of $\alpha$ is the same as those of $\beta$).

Given a grammar $G$ over the alphabet $\left\{ a, b, c\right\}$, determine whether $L(G)$ contains a string $x$ of which aaa occurs as a substring.

Given a grammar $G$ and a string $x \in L(G)$, determine whether there is a derivation of $x$ that does not contain a sentential form in which $a A a$ occurs as a substring, where $a$ is a terminal symbol and $A$ is a nonterminal symbol in $G$.

Given a grammar $G$ and a string $x \in L(G)$, determine whether there is a derivation of $x$ in which the lengths of the sentential forms do not decrease.

Given a grammar $G$ and a string $x \in L(G)$, determine whether there is a derivation of $x$ in which the lengths of the sentential forms decrease at most $n$ times, where $n=\left|x\right|$.

Given a context-free grammar $G$ and a DFA $M$, determine whether $L(G) \subseteq L(M)$.

Given a context-free grammar $G$ and a DFA $M$, determine whether $L(M) \subseteq L(G)$.

Given a context-free grammar $G$, determine whether $L(G)$ is regular.

Given a context-free grammar $G$, determine whether the complement of $L(G)$ is context-free.

Given two context-free grammars $G_{1}$ and $G_{2}$, determine whether $L\left(G_{1}\right) \cap L\left(G_{2}\right)$ is context-free.

The problem PCP over the alphabet $\Sigma =\left\{ 1\right\}$.

The problem PCP over the alphabet $\Sigma =\left\{ 0,1\right\}$.

Given a finite set of ordered pairs $\left(x_{1}, y_{1}\right), \ldots ,\left(x_{n}, y_{n}\right)$ of strings in $\Sigma^{*}$, determine whether there is an infinite sequence $(i_{1}, i_{2}, \ldots )$ of integers in $\left\{ 1, \ldots , n\right\}$ such that $x_{i_{1}} x_{i_{2}} \cdots =y_{i_{1}} y_{i_{2}} \cdots$.

Given a finite set of ordered pairs $\left(x_{1}, y_{1}\right), \ldots ,\left(x_{n}, y_{n}\right)$ of strings in $\Sigma^{*}$, determine whether there exist two sequences of integers ($i_{1}$, $\left.i_{2}, \ldots , i_{k}\right)$ and $\left(j_{1}, j_{2}, \ldots , j_{\ell }\right)$, with each element belonging to $\left\{ 1\text{, }\ldots , n\right\}$, such that $x_{i_{1}} x_{i_{2}} \cdots x_{i_{k}}=y_{j_{1}} y_{j_{2}} \cdots y_{j_{j}}$.

The same question as (d) above, except that the two sequences of integers must be of the same size, that is, $k=\ell$.