Упражнения

В этом упражнении речь идёт о МТ $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.