УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА С ДВУМЯ ВНУТРЕННИМИ СОСТОЯНИЯМИ

Введение

В известной статье А. М. Тьюринг определил класс вычислительных машин, называемых ныне машинами Тьюринга. Можно представить себе, что машина Тьюринга состоит из трех частей: управляющего элемента, считывающей и записывающей головки и бесконечной ленты. Лента разделена на последовательность квадратов, каждый из которых может хранить любой символ из конечного алфавита. Считывающая головка в каждый данный момент воспринимает один квадрат ленты. Она может прочесть записанный там символ и под действием управляющего элемента записать новый символ, а также передвинуться на один квадрат вправо или влево. Управляющий элемент представляет собой устройство с конечным числом внутренних «состояний». В каждый данный момент ближайшая операция машины определяется текущим состоянием управляющего элемента и символом, воспринимаемым считывающей головкой. Эта операция состоит из трех частей: 1) записи нового символа в воспринимаемом квадрате (новый символ, конечно, может совпадать с только что прочитанным); 2) перехода управляющего элемента в новое состояние (которое может совпадать с предыдущим состоянием); 3) движения считывающей головки на один квадрат вправо или влево.

При подготовке машины к работе на некоторый конечный кусок ленты наносится начальная последовательность символов, а остальная часть ленты оставляется пустой (т. е. заполненной некоторым «пустым» символом). Считывающая головка помещается в некотором начальном квадрате, и машина приступает к вычислениям согласно правилам своей работы. В первоначальной формулировке

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

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

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

Универсальная машина Тьюринга с двумя состояниями

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

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

состоянию 17 и в то же время сохраняющим информацию о предыдущем символе в этом квадрате. Процесс качания возвращает также старый квадрат к одному из элементарных символов (находящихся во взаимнооднозначном соответствии с символами, используемыми машиной А), а именно к тому элементарному символу, который должен быть записан в этом квадрате после окончания этой операции.

Формально машина В строится так. Пусть символы алфавита машины А суть и пусть ее состояния суть . В машине В поставим в соответствие алфавиту машины элементарных символов Вт. Затем определим новых символов, соответствующих парам из состояния и символа машины А, снабженных двумя новыми двузначными индексами. Эти символы обозначим через где (соответственно символам), (соответственно состояниям), или — (в зависимости от того, передает или получает информацию квадрат ленты во время качания) и или (в зависимости от того, вправо или влево от воспринимаемого квадрата должна передвинуться считывающая головка при качании).

Два состояния машины В назовем а и (3. Эти состояния используются двояко. Во-первых, при первом шаге качания они переносят в ближайший очередной квадрат информацию о том, вправо или влево от нового квадрата лежит старый. Эта информация нужна в новом квадрате, чтобы управляющий элемент передвинул считывающую головку назад в нужном направлении. После первого шага информация об этом сохраняется в новом квадрате с помощью записанного там символа (последний индекс Во-вторых, состояния используются, чтобы сообщить из старого квадрата в новый о конце качания. После первого шага качания состояние Р переносится в новый квадрат вплоть до конца качания, когда переносится а. Это означает конец операции, и новый квадрат начинает затем действовать как передатчик и управляет следующим шагом вычисления.

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

Продолжение (см. скан)

Эти операции пока что никак не зависят от таблицы работы машины А (кроме числа используемых символов). Операции же следующего и последнего типа формулируются в терминах таблицы работы моделируемой машины. Предположим, что машина А имеет формулу операций

Тогда по определению машина В имеет формулу

причем, если в формуле (6) употреблена верхняя буква то верхние буквы употребляются также и в формуле (7) и обратно.

Проследим цикл работы системы, состоящий из одной операции машины А и соответствующей серии операций машины В.

Пусть машина А читает символ и находится в состоянии и пусть ее таблицей работы предусмотрена запись символа переход в состояние и движение вправо. Машина В читает (по индуктивному предположению) символ [значение или зависит от предыдущих операций и безразлично для дальнейшего]. Машина В будет находиться в состоянии а. В соответствии с формулой машина В запишет , перейдет в состояние Р и передвинется вправо. Предположим, что квадрат справа в машине А содержит соответствующий квадрат в машине В содержит Приходя в этот квадрат в состоянии , машина В в силу формулы (2) записывает переходит в состояние а и движется назад, влево. Это служит началом переноса информации о состоянии с помощью процесса качания. Приходя в квадрат слева, машина В читает и в силу формулы (4) записывает , переходит в состояние (3 и передвигается опять

вправо. Затем в силу формулы (3) она записывает переходит в состояние а и возвращается налево. Весь ход процесса приведен в табл. 1.

Таблица 1 (см. скан)

Указанные операции завершают перенос информации о состоянии в квадрат справа и выполнение команды, отданной квадратом слева. В квадрате слева записан теперь символ (соответствующий символу в машине А), а в квадрате справа — символ считывающая головка находится на этом квадрате, имея внутреннее состояние а. Это возвращает нас к ситуации, аналогичной той, которая имела место в начале рассмотренного цикла. Рассуждая по индукции, видим, что машина В моделирует поведение машины А.

Чтобы заставить машину В работать аналогично машине А, заполним начальную ленту машины В соответственно начальной ленте машины А (с заменой на за исключением квадрата, занимаемого считывающей головкой в начальный момент. Если начальное состояние машины А и начальный символ в этом квадрате, то в соответствующем квадрате ленты машины В записываем и приводим В в состояние а.