Тезис Чёрча—Тьюринга

В этом упражнении речь идёт о МТ $M_{2}$, описание и диаграмма состояний которой приведены в примере 3.7. В каждом пункте приведите последовательность конфигураций, через которые проходит $M_{2}$, будучи запущенной на указанной входной строке.

В этом упражнении речь идёт о МТ $M_{1}$, описание и диаграмма состояний которой приведены в примере 3.9. В каждом пункте приведите последовательность конфигураций, через которые проходит $M_{1}$, будучи запущенной на указанной входной строке.

Измените доказательство теоремы 3.16, чтобы получить следствие 3.19, показывающее, что язык разрешим тогда и только тогда, когда его разрешает некоторая недетерминированная машина Тьюринга. (Вы можете использовать следующую теорему о деревьях. Если у каждого узла дерева конечное число потомков, и каждая ветвь дерева содержит конечное число узлов, то само дерево содержит конечное число узлов.)

Дайте формальное определение перечислителя. Считайте его разновидностью двухленточной машины Тьюринга, использующей свою вторую ленту как принтер. Включите в определение понятие перечисляемого языка.

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

В теореме 3.21 мы показали, что язык распознаётся машиной Тьюринга тогда и только тогда, когда его перечисляет некоторый перечислитель. Почему мы не использовали следующий более простой алгоритм для прямого направления доказательства? Как и раньше, $s_{1}, s_{2}, \ldots$ — список всех строк из $\Sigma^{*}$. $E=$ «Игнорировать вход.

1. Повторять следующее для $i=1,2,3, \ldots$. 2. Запустить $M$ на $s_{i}$. 3. Если она допускает, вывести $s_{i}$.»

Объясните, почему следующее не является описанием корректной машины Тьюринга. $M_{\text{bad }}=$ «На входе $\langle p\rangle$ — многочлене от переменных $x_{1}, \ldots , x_{k}$:

1. Перебрать все возможные наборы целочисленных значений $x_{1}, \ldots , x_{k}$. 2. Вычислить $p$ на всех этих наборах. 3. Если хотя бы на одном из этих наборов значение равно 0, допустить; иначе отвергнуть.»

Приведите описания машин Тьюринга на уровне реализации, разрешающих следующие языки над алфавитом 0,1.

Назовём $k$-МП-автоматом автомат с магазинной памятью, у которого $k$ стеков. Таким образом, 0-МП-автомат — это НКА, а 1-МП-автомат — это обычный МП-автомат. Вы уже знаете, что 1-МП-автоматы мощнее (распознают более широкий класс языков), чем 0-МП-автоматы.

Назовём однократно записывающей машиной Тьюринга однoленточную МТ, которая может изменить каждую клетку ленты не более одного раза (включая ту часть ленты, где записан вход). Покажите, что эта разновидность машины Тьюринга эквивалентна обычной модели машины Тьюринга. (Подсказка: в качестве первого шага рассмотрите случай, когда машина Тьюринга может изменять каждую клетку ленты не более двух раз. Используйте побольше ленты.)

Машина Тьюринга с двусторонне бесконечной лентой похожа на обычную машину Тьюринга, но её лента бесконечна как влево, так и вправо. Изначально лента заполнена пустыми символами, за исключением той части, где записан вход. Вычисление определяется как обычно, за исключением того, что головка никогда не встречает конец ленты, двигаясь влево. Покажите, что этот тип машины Тьюринга распознаёт класс языков, распознаваемых машиной Тьюринга.

Машина Тьюринга со сбросом влево похожа на обычную машину Тьюринга, но функция переходов имеет вид

Если $\delta (q, a)=(r, b$, RESET $)$, то когда машина находится в состоянии $q$ и читает $a$, головка машины перепрыгивает в левый конец ленты после того, как машина запишет $b$ на ленту и перейдёт в состояние $r$. Заметим, что у таких машин нет обычной возможности сдвинуть головку на один символ влево. Покажите, что машины Тьюринга со сбросом влево распознают класс языков, распознаваемых машиной Тьюринга.

Машина Тьюринга с «остаться на месте» вместо «влево» похожа на обычную машину Тьюринга, но функция переходов имеет вид

В каждый момент машина может сдвинуть головку вправо либо оставить её на том же месте. Покажите, что этот вариант машины Тьюринга не эквивалентен обычной версии. Какой класс языков распознают такие машины?

Автомат с очередью похож на автомат с магазинной памятью, за исключением того, что стек заменён очередью. Очередь — это лента, позволяющая записывать символы только на левом конце и читать только на правом конце. Каждая операция записи (назовём её «push») добавляет символ на левый конец очереди, а каждая операция чтения (назовём её «pull») читает и удаляет символ на правом конце. Как и в МП-автомате, вход помещается на отдельную ленту только для чтения, и головка на входной ленте может двигаться только слева направо. Входная лента содержит клетку с пустым символом сразу после входа, чтобы можно было обнаружить конец входа. Автомат с очередью допускает свой вход, переходя в любой момент в специальное допускающее состояние. Покажите, что язык распознаётся детерминированным автоматом с очередью тогда и только тогда, когда он распознаётся машиной Тьюринга.

Покажите, что совокупность разрешимых языков замкнута относительно операции

Покажите, что совокупность языков, распознаваемых машиной Тьюринга, замкнута относительно операции

• Пусть $B=\left\{ \left\langle M_{1}\right\rangle ,\left\langle M_{2}\right\rangle , \ldots \right\}$ — распознаваемый машиной Тьюринга язык, состоящий из описаний МТ. Покажите, что существует разрешимый язык $C$, состоящий из описаний МТ, такой, что для каждой машины, описанной в $B$, найдётся эквивалентная машина в $C$, и наоборот.

• Покажите, что язык разрешим тогда и только тогда, когда некоторый перечислитель перечисляет его в стандартном строковом порядке.

• Покажите, что у каждого бесконечного языка, распознаваемого машиной Тьюринга, есть бесконечное разрешимое подмножество.

• Покажите, что однoленточные МТ, которые не могут писать на той части ленты, где содержится входная строка, распознают только регулярные языки.

Пусть $c_{1} x^{n}+c_{2} x^{n-1}+\cdots +c_{n} x+c_{n+1}$ — многочлен с корнем при $x=x_{0}$. Пусть $c_{\text{max }}$ — наибольшее по модулю значение среди $c_{i}$. Покажите, что

Пусть $A$ — язык, содержащий единственную строку $s$, где

Разрешим ли $A$? Почему да или почему нет? Для целей этого упражнения считайте, что вопрос о том, будет ли найдена жизнь на Марсе, имеет однозначный ответ Да или Нет.