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

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

Пусть внешний алфавит состоит из пустого знака и вертикальной палочки |. В качестве «заменителя» пустого знака мы будем использовать знак 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, то становится ясным, что машина Тьюринга с такой программой осуществляет не что иное, как вычитание Единицы из любого числа, отличного от нуля. Если же предьявить ей пустую ленту, то машина выключится сразу.

3. Исходная конфигурация та же. Программа машины Тьюринга задается списком команд:

C1 Х Х Ck

C1 | X C2

С2 X П С1

Первый такт определится второй командой. Машина сотрет левую палочку и перейдет в новое состояние С2. Восприняв в этом состоянии пустую ячейку (в ней на предыдущем такте был стерт знак|), она сдвинет считывающе-записывающую головку по ленте вправо и вновь перейду в состояние С1. Такое стирание и передвижение вправо будет повторяться до тех пор, пока в состоянии С1 машина не увидит пустую ячейку (это случится, когда палочки будут исчерпаны). Тогда машина остановится. Если ленту, состоящую из одних пустых ячеек, отождествить с нулем, то можно считать, что машина с такой программой осуществляет ту же операцию, что и рекурсивная функция N¹ (х), но только над положительными целыми числами: если на ленте помещен единственный массив из n палочек, то машина перерабатывает ленту с такой конфигурацией в пустую ленту.

4. Исходная конфигурация та же. Программа такова:

C1 X | Сk

C1 | Л С1.

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

5. Исходная конфигурация:

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

(два массива палочек, разделенных одной пустой ячейкой;

число палочек в каждом массиве произвольно). Работа машины Тьюринга задается списком команд:

С1 | ПС2

С2 Х | С3

С2 | П С2

С3 Х Л С4

С3 | П С3

С4 Х Х Ck

C4 | X С4

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

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