Сводимость

Покажите, что $E Q_{\text{CFG }}$ неразрешим.

Покажите, что $E Q_{\mathrm{CFG}}$ ко-распознаваем.

Найдите соответствие в следующем экземпляре проблемы соответствий Поста.

Если $A \leq_{\mathrm{m}} B$, а $B$ — регулярный язык, следует ли отсюда, что $A$ — регулярный язык? Почему да или почему нет?

Покажите, что $A_{\mathrm{TM}}$ не сводится к $E_{\mathrm{TM}}$. Иными словами, покажите, что не существует вычислимой функции, сводящей $A_{\text{TM }}$ к $E_{\text{TM }}$. (Подсказка: используйте доказательство от противного и уже известные вам факты об $A_{\text{TM }}$ и $E_{\text{TM }}$.)

Покажите, что $\leq_{\mathrm{m}}$ является транзитивным отношением.

Покажите, что если $A$ распознаётся машиной Тьюринга и $A \leq_{\mathrm{m}} \bar{A}$, то $A$ разрешим.

В доказательстве теоремы 5.15 мы изменили машину Тьюринга $M$ так, чтобы она никогда не пыталась сдвинуть головку за левый край ленты. Предположим, что мы не внесли это изменение в $M$. Измените построение PCP, чтобы обработать этот случай.

Пусть $T=\left\{ \langle M\rangle \mid M \text{ — МТ, допускающая } w^{\mathcal{R}} \text{ всякий раз, когда она допускает } w\right\}$. Покажите, что $T$ неразрешим.

Рассмотрим задачу определения того, записывает ли двухленточная машина Тьюринга когда-либо непустой символ на свою вторую ленту, будучи запущенной на входе $w$. Сформулируйте эту задачу как язык и покажите, что она неразрешима.

Рассмотрим задачу определения того, записывает ли двухленточная машина Тьюринга когда-либо непустой символ на свою вторую ленту в ходе вычисления на каком-либо входе. Сформулируйте эту задачу как язык и покажите, что она неразрешима.

Рассмотрим задачу определения того, записывает ли однoленточная машина Тьюринга когда-либо пустой символ поверх непустого в ходе вычисления на каком-либо входе. Сформулируйте эту задачу как язык и покажите, что она неразрешима.

Бесполезное состояние машины Тьюринга — это состояние, в которое ни при каком входе никогда не попадают. Рассмотрим задачу определения того, есть ли у машины Тьюринга бесполезные состояния. Сформулируйте эту задачу как язык и покажите, что она неразрешима.

Рассмотрим задачу определения того, пытается ли машина Тьюринга $M$ на входе $w$ когда-либо сдвинуть головку влево, находясь в самой левой клетке ленты. Сформулируйте эту задачу как язык и покажите, что она неразрешима.

Рассмотрим задачу определения того, пытается ли машина Тьюринга $M$ на входе $w$ когда-либо сдвинуть головку влево в какой-либо момент вычисления на $w$. Сформулируйте эту задачу как язык и покажите, что она разрешима.

Пусть $\Gamma =\left\{ 0,1, \sqcup \right\}$ — ленточный алфавит для всех МТ в этой задаче. Определим функцию занятого бобра $B B: \mathcal{N} \longrightarrow \mathcal{N}$ следующим образом. Для каждого значения $k$ рассмотрим все МТ с $k$ состояниями, останавливающиеся, будучи запущенными на пустой ленте. Пусть $B B(k)$ — максимальное число единиц, остающихся на ленте среди всех таких машин. Покажите, что $B B$ не является вычислимой функцией.

Покажите, что проблема соответствий Поста разрешима над унарным алфавитом $\Sigma =\left\{ 1\right\}$.

Покажите, что проблема соответствий Поста неразрешима над двоичным алфавитом $\Sigma =\left\{ 0,1\right\}$.

В упрощённой проблеме соответствий Поста, SPCP, верхняя строка в каждой паре имеет ту же длину, что и нижняя строка. Покажите, что SPCP разрешима.

Докажите, что существует неразрешимое подмножество 1*.

Пусть $A M B I G_{\mathrm{CFG}}=\left\{ \langle G\rangle \mid G\text{ — неоднозначная КС-грамматика}\right\}$. Покажите, что $A M B I G_{\mathrm{CFG}}$ неразрешим. (Подсказка: используйте сведение от PCP. По данному экземпляру

проблемы соответствий Поста постройте КС-грамматику $G$ с правилами

где $\mathrm{a}_{1}, \ldots , \mathrm{a}_{k}$ — новые терминальные символы. Докажите, что это сведение работает.)

Покажите, что $A$ распознаётся машиной Тьюринга тогда и только тогда, когда $A \leq_{\mathrm{m}} A_{\text{TM }}$.

Покажите, что $A$ разрешим тогда и только тогда, когда $A \leq_{\mathrm{m}} 0^{*} 1^{*}$.

Пусть $J=\left\{ w \mid \text{либо } w=0 x \text{ для некоторого } x \in A_{\text{TM }}, \text{ либо } w=1 y \text{ для некоторого } y \in \overline{A_{\text{TM }}}\right\}$. Покажите, что ни $J$, ни $\bar{J}$ не распознаются машиной Тьюринга.

Приведите пример неразрешимого языка $B$, для которого $B \leq_{\mathrm{m}} \bar{B}$.

Назовём двухголовочным конечным автоматом (2DFA) детерминированный конечный автомат с двумя доступными только для чтения двунаправленными головками, которые начинают с левого конца входной ленты и могут независимо друг от друга двигаться в любом направлении. Лента 2DFA конечна и имеет размер, ровно достаточный для того, чтобы вместить вход плюс две дополнительные пустые клетки ленты — по одной на левом и на правом концах, — служащие разделителями. 2DFA допускает свой вход, переходя в специальное допускающее состояние. Например, 2DFA может распознавать язык $\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mathrm{c}^{n} \mid n \geq 0\right\}$.

Двумерный конечный автомат (2DIM-DFA) определяется следующим образом. Вход представляет собой прямоугольник размера $m \times n$ при произвольных $m, n \geq 2$. Клетки на границе прямоугольника содержат символ , а внутренние клетки содержат символы входного алфавита $\Sigma$. Функция переходов $\delta : Q \times (\Sigma \cup \left\{ \# \right\} ) \longrightarrow Q \times \left\{ \mathrm{L}, \mathrm{R}, \mathrm{U}, \mathrm{D}\right\}$ указывает следующее состояние и новое положение головки (влево, вправо, вверх, вниз). Машина допускает, когда переходит в одно из выделенных допускающих состояний. Она отвергает, если пытается выйти за пределы входного прямоугольника или если никогда не останавливается. Две такие машины эквивалентны, если они допускают одни и те же прямоугольники. Рассмотрим задачу определения того, эквивалентны ли две такие машины. Сформулируйте эту задачу как язык и покажите, что она неразрешима.

• Теорема Райса. Пусть $P$ — произвольное нетривиальное свойство языка машины Тьюринга.

Более формально, пусть $P$ — язык, состоящий из описаний машин Тьюринга, причём $P$ удовлетворяет двум условиям. Во-первых, $P$ нетривиален — он содержит некоторые, но не все описания МТ. Во-вторых, $P$ является свойством языка МТ — как только $L\left(M_{1}\right)=L\left(M_{2}\right)$, выполняется $\left\langle M_{1}\right\rangle \in P$ тогда и только тогда, когда $\left\langle M_{2}\right\rangle \in P$. Здесь $M_{1}$ и $M_{2}$ — произвольные МТ. Докажите, что $P$ — неразрешимый язык.

Покажите, что оба условия из задачи 5.28 необходимы для доказательства неразрешимости $P$.

Задача 5.28 (теорема Райса): Пусть $P$ — язык, состоящий из описаний машин Тьюринга, причём $P$ удовлетворяет двум условиям. Во-первых, $P$ нетривиален — он содержит некоторые, но не все описания машин Тьюринга. Во-вторых, $P$ является свойством языка машины Тьюринга — всякий раз, когда $L\left(M_{1}\right)=L\left(M_{2}\right)$, имеем $\left\langle M_{1}\right\rangle \in P$ тогда и только тогда, когда $\left\langle M_{2}\right\rangle \in P$. Здесь $M_{1}$ и $M_{2}$ — произвольные машины Тьюринга.

Используя теорему Райса из задачи 5.28, докажите неразрешимость каждого из следующих языков.

Пусть

для произвольного натурального числа $x$. Если начать с целого числа $x$ и итерировать $f$, получится последовательность $x, f(x), f(f(x)), \ldots$. Остановимся, если когда-либо достигнем 1. Например, при $x=17$ получаем последовательность 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Обширные компьютерные проверки показали, что любая начальная точка от 1 до некоторого большого положительного целого числа даёт последовательность, заканчивающуюся на 1. Но вопрос о том, приходят ли все положительные начальные точки к 1, остаётся нерешённым; он называется проблемой $3 x+1$. Предположим, что $A_{\text{TM }}$ разрешалась бы некоторой МТ $H$. Используя $H$, опишите МТ, которая гарантированно даст ответ на проблему $3 x+1$.

Докажите, что следующие два языка неразрешимы.

Рассмотрим задачу определения того, допускает ли МП-автомат хотя бы одну строку вида $\left\{ w w \mid w \in \left\{ 0,1\right\}^{*}\right\}$. Используя метод истории вычисления, покажите, что эта задача неразрешима.

Пусть $X=\left\{ \langle M, w\rangle \mid M\text{ — однoленточная МТ, которая никогда не изменяет ту часть ленты, где записан вход }w\right\}$. Разрешим ли $X$? Докажите свой ответ.

Будем говорить, что переменная $A$ в КС-грамматике $G$ необходима, если она встречается в каждом выводе некоторой строки $w \in G$. Пусть $N E C E S S A R Y_{\mathrm{CFG}}=\left\{ \langle G, A\rangle \mid A\text{ — необходимая переменная в }G\right\}$.

• Будем говорить, что КС-грамматика минимальна, если ни одно из её правил нельзя удалить, не изменив порождаемый язык. Пусть $M I N_{\mathrm{CFG}}=\left\{ \langle G\rangle \mid G\text{ — минимальная КС-грамматика}\right\}$.