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

• Название: Жар холодных числ и пафос бесстрастной логики
• Автор: Борис Бирюков
• Издательство: Издательство "Знание"
• Жанр: Математика
• Год: 1977

Цель книги доктора философских наук Б. В. Бирюкова и кандидата философских наук В. Н. Тростникова - создать общую картину подготовки и развития логико-математических аспектов кибернетики. Авторы рассказывают о длительном развитии науки логики, возникшей еще в Древней Греции, прослеживают непрерывающуюся нить преемственности, тянущуюся от Аристотеля к "чуду XX века" - быстродействующим кибернетическим устройствам.

---

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

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

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

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

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

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