Машины Тьюринга

Построить машину Тьюринга, выполняющую следующую задачу: по входу, состоящему из одного или нескольких слов $w_{1} \Lambda \ldots \Lambda w_{n}$ в алфавите $\Sigma$ (возможно, что $n=1$), построить выход, удвоив последнее из слов: $w_{1} \Lambda \ldots \Lambda w_{n} \Lambda w_{n}$.

Построить машину Тьюринга, сравнивающую два входных слова в алфавите $\left\{ a, b, c\right\}$ лексикографически. Она должна вычислять словарную функцию:

Построить программы машин Тьюринга, вычисляющих следующие словарные функции в алфавите $\Sigma =\left\{ a, b, c\right\}$ :

Построить машину Тьюринга для перевода записи числа из двоичной системы в унарную, входной алфавит $\left\{ 0,1\right\}$.

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

Даны машины Тьюринга со стандартной заключительной конфигурацией $\mathfrak {M}_{i}$, каждая из которых вычисляет словарную функцию $f_{i}(x)$ за время $t_{i}(x)$, $i=1, \ldots , n$. Указать, как построить, и оценить время работы

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

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

Реализовать машину Тьюринга из примеров 111 на стр. 409 и 112 на стр. 410 без расширения алфавита.

Пример 111: машина Тьюринга в алфавите $\Sigma =\left\{ a,b,c\right\}$, вычисляющая функцию $f\left(w_{1}w_{2}\right)=w_{1}$ для слов, у которых $\left|w_{1}\right|-\left|w_{2}\right| \in \left\{ 0,1\right\}$ (то есть стирающая вторую половину слова, оставляя центральный символ, если длина нечётная), реализованная с расширением алфавита штрихованными символами $a^{\prime }, b^{\prime }, c^{\prime }$.

Пример 112: машина Тьюринга в алфавите $\Sigma =\left\{ 0,1\right\}$, складывающая два непустых двоичных числа, записанных на ленте, реализованная с расширением алфавита штрихованными символами $0^{\prime }, 1^{\prime }$.

Завершить построение машины Тьюринга из теоремы 156 на стр. 413.

Теорема 156: Для всякой машины Тьюринга $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ можно построить $\Sigma$-эквивалентную машину Тьюринга $\mathfrak {N}$, имеющую стандартную заключительную конфигурацию (то есть такую, что в момент остановки головка находится в нулевой ячейке, а на ленте записан только результат без вспомогательных символов-меток).

Другой, по сравнению с конструкцией теоремы 157 на стр. 417, подход к моделированию двухсторонней ленты на односторонней заключается в том, чтобы содержимое неотрицательной половины ленты $\mathfrak {M}$ хранить в ячейках с нечётными номерами, а содержимое левой половины — с чётными. То есть новая лента будет иметь вид $\beta (0)=\# , \beta (2 x+1)=\alpha (x)$ и $\beta (2 x)=\alpha (-x)$ при $x>0$. Построить программу односторонней машины $\mathfrak {N}$, реализующую этот подход.

Теорема 157: Для всякой машины Тьюринга $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ существует $\Sigma$-эквивалентная односторонняя машина Тьюринга $\mathfrak {N}$, имеющая стандартную заключительную конфигурацию. (Конструкция из доказательства теоремы 157 «складывает» двухстороннюю ленту пополам с помощью двухэтажных символов: ячейка $i$ ленты $\mathfrak {N}$ хранит пару, где сверху — символ из ячейки $i+1 \geqslant 0$ ленты $\mathfrak {M}$, а снизу — символ из ячейки $-i \leqslant 0$; в этой задаче требуется предложить альтернативный способ кодирования без двухэтажных символов, достигающий той же цели.)

Доказать, что односторонняя машина Тьюринга $\mathfrak {N}$, построенная в теореме 157 на стр. 417, корректно моделирует исходную машину $\mathfrak {M}$.

Теорема 157: Для всякой машины Тьюринга $\mathfrak {M}=(Q, \Sigma , P, q_{0})$ существует $\Sigma$-эквивалентная односторонняя машина Тьюринга $\mathfrak {N}$, имеющая стандартную заключительную конфигурацию. (В доказательстве конструкция использует двухэтажные символы, чтобы «сложить» двухстороннюю ленту машины $\mathfrak {M}$ пополам: ячейка $i$ ленты $\mathfrak {N}$ хранит пару, верхний этаж которой — это ячейка $i+1$ ленты $\mathfrak {M}$, а нижний — ячейка $-i$, так что неотрицательные и отрицательные ячейки ленты $\mathfrak {M}$ чередуются на односторонней ленте $\mathfrak {N}$.)

Показать, как извлечь из кода ленты $\rho (\alpha )$ выходные слова (теорема 159 на стр. 426).

Для односторонней ленты $\alpha$ в алфавите $\Sigma =\left\{ a_{0}, a_{1}, \ldots , a_{k}\right\}$ (где $a_{0}=\Lambda$), содержащей в каждый момент последовательность $\# a_{i_{1}} a_{i_{2}} \ldots a_{i_{n}} \Lambda \Lambda \ldots$, код ленты определяется как $\rho (\alpha )=\sum_{j=1}^{\infty } \alpha (j) \cdot k^{j-1}$, то есть последовательность индексов символов читается как цифры числа в $k$-ичной системе счисления (в этой сумме лишь конечно много слагаемых ненулевые). Теорема 159: каждая вычислимая по Тьюрингу словарная функция является программно вычислимой — в доказательстве машина Тьюринга $\mathfrak {M}$ моделируется программой с метками $\Pi$, которая хранит конфигурацию $(q, i, \alpha )$ машины $\mathfrak {M}$ с помощью переменной $r$, содержащей код ленты $\rho (\alpha )$; в конце полученный код ленты нужно раскодировать обратно в последовательность выходных слов — именно это и требуется в данной задаче.

Показать, как на машине Тьюринга построить унарную запись входа и по унарной записи восстановить выход (теорема 160 на стр. 429) без расширения алфавита.

Теорема 160: Если словарная функция $f:\Omega^{*} \rightarrow \Omega^{*}$ вычислима на машине Тьюринга $\mathfrak {M}=(Q, \Sigma , P, q_{0})$, $\Omega \subseteq \Sigma$, то она вычислима на односторонней машине Тьюринга $\mathfrak {N}=(Q^{\prime }, \Sigma^{\prime }, P^{\prime }, q_{0}^{\prime })$ без расширения алфавита, то есть $\Sigma^{\prime }=\Omega \cup \left\{ \Lambda , \# \right\}$. (В доказательстве машина $\mathfrak {N}$ строится так: сначала по входу строится унарная запись его кода ленты $\rho (\alpha_{0})$, затем запускается машина $\mathfrak {N}_{1}$, вычисляющая ту же функцию на этой унарной записи — она даётся теоремой 158, — и, наконец, по унарной записи получившегося кода ленты восстанавливается сам выход; в этой задаче требуется реализовать именно эти два шага перекодировки.)

Показать, как промоделировать на машине Тьюринга работу программы с метками в двоичной системе (теорема 158 на стр. 422).

Теорема 158: Каждая программно вычислимая функция $f$ вычислима по Тьюрингу без расширения алфавита. (В доказательстве программа с метками $\Pi$ с переменными $x_{1}, \ldots , x_{k}$ моделируется односторонней машиной Тьюринга, конфигурация которой $(q_{\alpha }, 0, \kappa )$ соответствует конфигурации $(\alpha , \sigma )$ программы $\Pi$, а на ленте последовательно хранятся унарные записи значений $\sigma (x_{1}), \ldots , \sigma (x_{k})$, разделённые пустыми символами; там в качестве системы счисления выбрана унарная, а в этой задаче требуется показать, что подходит и двоичная.)

Построить универсальную машину Тьюринга, реализовав пункты 1)-21) из теоремы 161 на стр. 430.

Теорема 161: Для любого алфавита $\Sigma$ существует $\Sigma$-универсальная машина Тьюринга $\mathfrak {U}$, то есть такая машина, что для всякой машины Тьюринга $\mathfrak {M}=(Q,\Sigma ,P,q_{0})$ найдётся вход $c_{\mathfrak {M}}$ (кодирующий программу $\mathfrak {M}$), для которого при любом входе $x$ выполнено $\mathfrak {U}(c_{\mathfrak {M}}, x) = \mathfrak {M}(x)$.