Неразрешимые проблемы

Дана ДМТ $M$ и строка $y$; определите, останавливается ли $M$ на некотором входе $z$, который больше либо равен $y$.

Даны две ДМТ $M_{x}$ и $M_{y}$; определите, эквивалентны ли они (т. е. вычисляют ли они одну и ту же функцию).

Даны ДМТ $M$, вход $y$ и состояние $q_{i}$ машины $M$; определите, переходит ли $M$ когда-либо в состояние $q_{i}$ в вычислении на входе $y$.

Дана ДМТ $M$; определите, содержит ли вычисление $M(111)$ конфигурацию, в которой лента содержит подстроку 000.

Дана грамматика $G$ и строка $x$; определите, верно ли, что $x \in L(G)$.

Даны грамматика $G$ и две строки $x$ и $y$; определите, верно ли, что $x \xrightarrow [G]{*} y$.

Даны грамматика $G$ и две строки $x, y \in L(G)$; определите, существует ли вывод строки $x$, более длинный, чем кратчайший вывод строки $y$. (Длиной вывода называется число сентенциальных форм в этом выводе.)

Дана грамматика $G$; определите, верно ли, что $L(G)=\emptyset$.

Даны две грамматики $G_{1}$ и $G_{2}$; определите, верно ли, что $L\left(G_{1}\right) \subseteq L\left(G_{2}\right)$.

Дана грамматика $G$; определите, является ли $L(G)$ контекстно-свободным языком (т. е. для данной неограниченной грамматики $G$ определите, существует ли эквивалентная ей контекстно-свободная грамматика).

Даны однонаправленная одноленточная ДМТ $M$ (определённая в разделе 4.1) и строка $x$; определите, посетит ли когда-либо считывающая головка машины $M$ $(2n)$-ю ячейку в вычислении $M$ на входе $x$, где $n=\left|x\right|$ (крайнюю левую ячейку ленты мы называем 0-й ячейкой, следующую за ней справа — первой ячейкой и т. д.).

Даны двунаправленная одноленточная ДМТ $M$ (определённая в разделе 4.3) и строка $x$; определите, посетит ли когда-либо считывающая головка машины $M$ $(2n)$-ю ячейку в вычислении $M$ на входе $x$, где $n=\left|x\right|$ (ячейку, содержащую крайний левый символ строки $x$, мы называем первой ячейкой, следующую за ней справа — второй ячейкой и т. д.).

Даны двунаправленная одноленточная ДМТ $M$ и строка $x$; определите, сдвинется ли считывающая головка машины $M$ влево более чем $n$ раз (не обязательно подряд идущими шагами) в вычислении $M$ на входе $x$, где $n=\left|x\right|$.

Даны двунаправленная одноленточная ДМТ $M$, множество ленточных символов которой $\Gamma =\left\{ a, b, \mathrm{~ B}\right\}$, и строка $x \in \left\{ a, b\right\}^{*}$; определите, перезапишет ли машина $M$ когда-либо символ $a$ символом $b$ в вычислении на входе $x$.

Даны две ДМТ $M_{1}$ и $M_{2}$ и две строки $x_{1}$ и $x_{2}$; определите, верно ли, что в какой-то момент вычисления $M_{1}$ на входе $x_{1}$ и вычисления $M_{2}$ на входе $x_{2}$ первые три ячейки их лент содержат одинаковые символы (т. е. существует ли конфигурация $\alpha$ вычисления $M_{1}\left(x_{1}\right)$ и конфигурация $\beta$ вычисления $M_{2}\left(x_{2}\right)$, такие что первые три ленточных символа конфигурации $\alpha$ совпадают с первыми тремя символами конфигурации $\beta$).

Дана грамматика $G$ над алфавитом $\left\{ a, b, c\right\}$; определите, содержит ли $L(G)$ строку $x$, в которой aaa встречается в качестве подстроки.

Даны грамматика $G$ и строка $x \in L(G)$; определите, существует ли вывод строки $x$, не содержащий сентенциальной формы, в которой $a A a$ встречается в качестве подстроки, где $a$ — терминальный символ, а $A$ — нетерминальный символ грамматики $G$.

Даны грамматика $G$ и строка $x \in L(G)$; определите, существует ли вывод строки $x$, в котором длины сентенциальных форм не убывают.

Даны грамматика $G$ и строка $x \in L(G)$; определите, существует ли вывод строки $x$, в котором длины сентенциальных форм убывают не более $n$ раз, где $n=\left|x\right|$.

Даны контекстно-свободная грамматика $G$ и ДКА $M$; определите, верно ли, что $L(G) \subseteq L(M)$.

Даны контекстно-свободная грамматика $G$ и ДКА $M$; определите, верно ли, что $L(M) \subseteq L(G)$.

Дана контекстно-свободная грамматика $G$; определите, является ли $L(G)$ регулярным.

Дана контекстно-свободная грамматика $G$; определите, является ли дополнение $L(G)$ контекстно-свободным.

Даны две контекстно-свободные грамматики $G_{1}$ и $G_{2}$; определите, является ли $L\left(G_{1}\right) \cap L\left(G_{2}\right)$ контекстно-свободным.

Задача PCP над алфавитом $\Sigma =\left\{ 1\right\}$.

Задача PCP над алфавитом $\Sigma =\left\{ 0,1\right\}$.

Дано конечное множество упорядоченных пар $\left(x_{1}, y_{1}\right), \ldots ,\left(x_{n}, y_{n}\right)$ строк из $\Sigma^{*}$; определите, существует ли бесконечная последовательность $(i_{1}, i_{2}, \ldots )$ целых чисел из $\left\{ 1, \ldots , n\right\}$, такая что $x_{i_{1}} x_{i_{2}} \cdots =y_{i_{1}} y_{i_{2}} \cdots$.

Дано конечное множество упорядоченных пар $\left(x_{1}, y_{1}\right), \ldots ,\left(x_{n}, y_{n}\right)$ строк из $\Sigma^{*}$; определите, существуют ли две последовательности целых чисел ($i_{1}$, $\left.i_{2}, \ldots , i_{k}\right)$ и $\left(j_{1}, j_{2}, \ldots , j_{\ell }\right)$, каждый элемент которых принадлежит $\left\{ 1\text{, }\ldots , n\right\}$, такие что $x_{i_{1}} x_{i_{2}} \cdots x_{i_{k}}=y_{j_{1}} y_{j_{2}} \cdots y_{j_{j}}$.

Тот же вопрос, что и в пункте (d) выше, но с тем условием, что обе последовательности целых чисел должны быть одинакового размера, то есть $k=\ell$.