Жар холодных числ и пафос бесстрастной логики

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

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

На этот раз объектами — и теми, которые задаются в качестве исходных, и теми, которые вычисляются, являются непосредственно уже не числа, а некоторые слова: конфигурации из стандартных символов, или знаков некоторого алфавита. Но что препятствует отождествлять числа с их знаковыми кодами — с их записью, например, в обычной системе счисления или со словами из вертикальных палочек? Такой подход тем более естествен, что речь идет о передаче вычислительных операций машине, которая «понимает» только знаки. Машина Тьюринга может перерабатывать слова, являющиеся кодами чисел, в частности, осуществлять операции, выполняемые рекурсивными функциями, принятыми за исходные, следовательно, может успешно работать в качестве «арифметической машины».

Раз мы не смотрим на машину Тьюринга как на конструкцию «в металле», мы должны описать схему ее работы таким способом, чтобы не возникало неоднозначностей в понимании и трудностей в ее анализе. Для этого надо задать программу тьюринговой машины, в которой будет указано, какие акты поведения соответствуют каждой возможной паре «обозреваемый знак — внутреннее состояние». Такая программа может строиться следующим образом. Поскольку внутренних состояний и типов знаков конечное число, мы можем выписать столбец всех пар «внутреннее состояние — знак». Число этих пар равно произведению числа внутренних состояний на число знаков алфавита, включая пустой знак. Против каждой из пар выпишем другую пару:

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

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

1. Конфигурация на ленте представлена следующим расположением вертикальных палочек:

... X X X | | | | | ... | | | | | X X X ...

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

С1 | | Сk

(четверки, до которых при переработке заданной конфигурации дело заведомо дойти не может, обычно не выписывают).