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

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

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

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

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

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

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

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

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

С1 | | Сk

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

Вначале машина нацелена на самую левую палочку. Внутреннее состояние машины в начальный момент есть С1 поэтому данная четверка как раз и дает информацию о действии машины. Как видно из структуры четверки, машина должна стереть единицу и вновь ее восстановить, а затем перейти в состояние Сk, то есть остановиться. Понятно, что конфигурация, написанная на ленте, при этом не изменится; это верно для любого количества палочек. Это — пример «тождественной» машины Тьюринга.

2. Алфавит тот же, исходное слово то же. Программа машины представляет собой список из двух команд:

С1 Х Х Сk

С1 | Х С1

(и здесь — как и в дальнейших примерах — четверки, до использования которых дело не дойдет, опускаются). Как произойдет первый такт работы машины, указывает вторая команда, поскольку в ее левой части стоят как раз те параметры, которые характеризуют исходную ситуацию. Выполняя эту команду, машина сотрет палочку и сохранит прежнее внутреннее состояние С1. В следующем такте она воспримет пустую ячейку, оставит ее пустой и «отключится». Если отождествить слово из n палочек (n = 1, 2,...) с числом n, то становится ясным, что машина Тьюринга с такой программой осуществляет не что иное, как вычитание Единицы из любого числа, отличного от нуля. Если же предьявить ей пустую ленту, то машина выключится сразу.