10.2. Машины Тьюринга и программы

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

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

Следует уточнить, однако, что мы имеем в виду, так как для машин Тьюринга исходное данное и результат были двоичными словами, а для программ — натураль­ными числами. Мы отождествляем те и другие по есте­ственному правилу, при котором слова А (пустое), 0, 1, 00, 01, ... соответствуют числам 0, 1, 2, 3, 4 ... (чтобы получить из числа слово, прибавим к нему единицу, пере­ведём в двоичную систему и отбросим единицу в старшем разряде).

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

Чтобы решить, как удобнее кодировать содержимое ленты слева и справа от головки, заметим, что маши­на Тьюринга обращается с двумя половинами лентами слева и справа от головки как со стеками. (Стеком назы­вается структура данных, напоминающая стопку листов. В неё можно положить лист наверх, взять верхний лист, а также проверить, есть ли ещё листы.) В самом деле, при движении головки направо из правого стека берётся верхний элемент, а в левый стек кладётся; при движении налево — наоборот. Стеки легко моделировать с помо-

Машины Тьюринга и программы

щью чисел: например, если в стеке хранятся символы О и 1, то добавление нуля соответствует операции х >—у 2х, добавление единицы — операции х н->- 2х + 1, верхний элемент есть остаток при делении на 2, а удаление верх­него элемента есть деление на 2 (с отбрасыванием остат­ка). Другими словами, мы воспринимаем двоичную за­пись числа как стек, вершина которого находится спра­ва, у младшего разряда. Точно так же можно использо­вать п-ичную систему счисления и представить стек с п возможными символами в каждой позиции.

Теперь основной цикл машины Тьюринга можно за­писать как программу, оперирующую с указанными че­тырьмя числами (символ, состояние, левый стек и пра­вый стек) — без особых хитростей. Но несколько вещей всё-таки надо иметь в виду.

Во-первых, стеки конечны, а лента бесконечна — мы должны договориться, что если стек опустошается, то в него автоматически добавляется символ пробела. Тем самым бесконечный пустой хвост ленты может присут­ствовать в стеке, как теперь говорят, виртуально.

Во-вторых, напомним, что мы договорились отож­дествлять двоичные слова (которые подаются на вход машины Тьюринга) и их коды (которые хранятся в пере­менных нашей программы). Поэтому, получив код вход­ного слова, надо его разобрать по символам и положить эти символы один за другим в стек (основания систем счисления разные, так что просто так переписать это нельзя). Аналогичные проблемы возникают и при пре­вращении выхода (части содержимого правого стека) в соответствующее число, но все они легко преодолимы, и мы не будем вдаваться в подробности. >

Верно и обратное утверждение:

Теорема 66. Всякая функция, вычислимая програм­мой с конечным числом переменных, вычислима на ма­шине Тьюринга.

<] Нам надо моделировать поведение программы с по­мощью машины Тьюринга. Будем считать, что значения переменных записаны на ленте (в двоичной системе) и разделены специальным разделительным символом. То­г да машина может найти любую переменную, идя от на­чала ленты и считая разделительные символы, сделать что-то с этой переменной и затем вернуться обратно в начало. (Нет необходимости записывать на ленте номер исполняемой команды, поскольку команд конечное число и машина может помнить номер текущей команды как часть своего состояния.) Операции прибавления и вычи­тания единицы также легко выполнимы в двоичной за­писи (если идти справа налево). Надо только иметь в ви­ду, что размер числа может увеличиться, и тогда нужно для него освободить место, сдвинув все символы спра­ва от головки на одну позицию. (При уменьшении нужно сдвинуть влево.) Ясно, что это также легко выполнить с помощью машины Тьюринга.

Если мы записываем числа в двоичной системе, то проблемы с перекодированием при вводе-выводе мини­мальны (надо лишь дописать нули для значений осталь­ных переменных в начале работы и встать в нужное ме­сто ленты в конце). >