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

Автор книги: Борис Бирюков

Соавторы: В. Тростников
сообщить о нарушении

Текущая страница: 10 (всего у книги 14 страниц)

(4) остановиться (например, отключиться от сети, если она электрическая); остановку машины можно понимать как ее переход в особое – заключительное – состояние.

Больше ничего машина Тьюринга делать не способна.

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

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

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

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

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

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

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

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

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

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

Здесь мы наблюдаем действие живой «машины Тьюринга», описание которой исключительно просто. Обозначим обычное состояние кошки через С1, состояние испуга через С2, движение вверх по сосне через П, движение вниз через Л, вид подножья сосны зашифруем символом |, вид, открывающийся с верхушки сосны, символом X. Тогда наша «машина Тьюринга» будет задана списком четверок:

C1 X X C2

C1 | П C1

C2 X Л C2

C2 | | C1

Убедимся, что данная программа имитирует поведение нашей кошки. На ленте написана единственная палочка (остальные ячейки пусты); эту палочку воспринимает машина, находящаяся в состоянии С1. В соответствии со второй командой считывающе-записывающая головка машины сделает движение по ленте вправо (кошка залезет на сосну) и останется в том же состоянии (кошка еще не испугалась). Второй такт работы машины определит первая команда:

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

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

Наконец, рассмотрим еще один подход к понятию вычислимости, разработанный А. А. Марковым. Ведущий отечественный «математический конструктивиста поставил перед собой вопрос: к каким элементарным и математически точно определимым операциям можно было бы свести все процедуры, широко применяющиеся в математике и других науках и носящие название процессов, задаваемых алгоритмами? Известно, что математика прямо-таки изобилует алгоритмами – четкими предписаниями о подлежащих выполнению действиях. Но задача состояла в нахождении общего определения алгоритма (алгорифма) – определения, под которое подпадали бы не только все известные алгоритмы, но и те, которые появятся в будущем. Искомое точное определение алгоритма должно было соответствовать содержательно-интуитивному пониманию алгоритмов в математике: алгоритм – это «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых исходных данных к искомому результату»^[12]. Для построения такого определения необходимо было найти «атомы», из которых можно сформировать любое предписание – общепонятное, ясное, однозначно понимаемое. Задача эта была очень важна. Вот как раскрывает ее особую роль известный отечественный специалист по философским проблемам математики С. А. Яновская (1896—1966).

«Начиная с глубокой древности математики строили алгоритмы ... для решения целых классов задач определенного рода. Таковы, например: всем известный алгоритм Эвклида, представляющий собой программу действий, которые нужно выполнить, чтобы, имея любые два целых числа a и b, отыскать их общий наибольший делитель; алгоритм Штурма, позволяющий по заданию коэффициентов многочлена отделить его корни; многие другие алгоритмы алгебры, теории чисел, дифференциальных уравнений и многие, многие другие.

Когда какой-нибудь алгоритм отыскан, то всем ясно что он уже есть: его существование не приходится доказывать.

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

Для этого нужно знать, что, собственно, ищут; нужно иметь четкое определение алгоритма, позволяющее оперировать с этим понятием, как с математическим объектом»^[13].

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

«10. Задача о разрешимости диофантова уравнения.

Пусть задано диофантово уравнение^[14] с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах»^[15].

Как мы видим из этого текста, эта проблема была поставлена Гильбертом на интуитивно-содержательном уровне, поэтому для ее решения нужно было проделать огромный путь, развить целые теории, разработать новые математические понятия. Ф. П. Варпаховский и А. Н. Колмогоров, говоря о теории алгоритмов, замечают:

«Оглядываясь на пройденный путь, математики должны быть благодарны десятой проблеме Гильберта уже за то, что она послужила одним из стимулов для создания этой теории»^[16]. Решение этой проблемы – решение отрицательное, доказывающее невозможность соответствующего алгоритма, было получено постепенно, усилиями ряда математиков; завершающий результат принадлежит представителю «четвертого поколения» марковской школы Ю. В. Матиясевичу, добившемуся успеха через 70 лет после постановки проблемы Гильбертом^[17].

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

В начале 50-х годов в работах А. А. Маркова (первые публикации которого по теории алгоритмов относятся ко второй половине 40-х годов) получила развитие та идея, что все математические алгоритмы можно свести к повторению одной элементарной операции, выполняемой в строгом соответствии с начертанным на бумаге предписанием, которое после очень простого объяснения на естественном языке или даже демонстрации нескольких примеров становится ясным каждому человеку и всеми людьми понимается одинаково. В 1951 году в «Трудах Математического института АН СССР» (т. XXXVIII) была помещена статья А. А. Маркова «Теория алгорифмов», излагающая новую концепцию, а в 1954 году вышла его большая монография^[18]. Ныне она, как и работы Чёрча и Тьюринга, является классической.

Марковские алгоритмы, которым их автор дал название «нормальных алгорифмов», работают над словами в каких-либо алфавитах, перерабатывая их в (другие) слова. Алгорифм состоит из вертикального списка команд (их называют формулами подстановок), каждая из которых имеет вид либо P → •Q, либо Q → P где P и Q – слова в некотором алфавите, не содержащем знаков • и →. Рассмотрим прежде всего действие отдельной формулы подстановки. Пусть в алфавите А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, —, +, =} дано слово 12 – 11 = 1 и команда

1 → 2.

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

22—11=1.

Если мы данную команду применим к этому слову, то получим:

22—21=1.

Следующие применения дадут:

22—22=1,

22—22=2.

Пытаясь применить команду в пятый раз, мы обнаружим, что в слове нет уже «подслова», совпадающего с левой частью команды. Команда, таким образом, перестанет срабатывать, и процесс применения данной формулы подстановки оборвется.

По существу, мы рассмотрели пример нормального алгорифма—алгорифма, состоящего из единственной команды. Если бы команда была не одна, то пользование алгорифмом не стало бы сложнее: в случае, когда самая верхняя команда не срабатывает, надо переходить к следующей команде; если и она не сработает, к следующей, и т. д. После срабатывания некоторой команды происходит возврат к самой верхней команде и ее проверка на применимость к полученному только-что слову и т. д. Если в ходе этого процесса встретится команда, содержащая после стрелки точку, процесс останавливается и слово, полученное в результате применения этой команды (называемой заключительной), объявляется результатом работы алгорифма.

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

Описанные правила настолько элементарны, что мы предоставляем читателю самостоятельно проследить за действием алгорифма

1 → 2

2 → 3

3 → 444,

примененного к слову 12—11 = 1. Для контроля мы выпишем последовательность слов, получаемых после каждого применения подходящей команды, разделяя их точкой с запятой: 12—11 = 1 (исходное слово);

22—11=1; 22—21 = 1; 22 – 22 = 1; 22 – 22 = 2; 32 – 22 = 2;

33 —22 =2; 33 – 32 = 2; 33 – 33 = 2; 33 – 33 = 3; 4443 – 33 = 3;

444444 – 33 = 3; 444444 – 4443 = 3; 444444 – 444444 = 3;

444444 – 444444 = 444.

На последнем слове процесс оборвется, и оно окажется результатом. В этом случае говорят, что данный алгорифм переработал слово 12—11=1 в слово 444444 – 444444 = 444.

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

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

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

Это значит, что рекурсивные функции и машины Тьюринга «равнообъемны» нормальным алгорифмам и что тезисы Чёрча и Тьюринга получают подкрепление в виде принципа нормализации (это название предложено А. А. Марковым; можно условиться называть этот принцип и по-другому, например, тезисом Маркова): всякое точное общепонятное предписание, определяющее произвольный потенциально осуществимый процесс переработки слов в каком-либо алфавите, ведущий от варьируемых исходных данных к некоторому результату, эквивалентно некоторому нормальному алгорифму.

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

Как и Чёрч в статье 1936 года, А. А. Марков приводит в своей фундаментальной монографии «Теория алгорифмов» ряд аргументов в пользу принципа нормализации. Как и у Чёрча, это не доказательства, а только соображения, к которым можно отнести прилагательное «убедительные». Они апеллируют прежде всего к практике математики. Исследования Маркова, давшие ему возможность найти разумные основания для подкрепления его тезиса, следует считать важным этапом в становлении основной гипотезы теории алгоритмов (теории эффективной вычислимости) – гипотезы, общий смысл которой состоит в утверждении, что различные, оказавшиеся эквивалентными друг другу, уточнения идеи алгоритма и вычислимости – рекурсивные функции, тьюринговы машины, нормальные алгорифмы^[19] – исчерпывающим образом описывают (каждое – в терминах своего специфического языка) эту идею.

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

Не так ли обстоит дело и в отношении основной гипотезы-теории алгоритмов в ее различных спецификациях– тезисов Чёрча, Тьюринга, Маркова? Вот что, например, говорит о своем тезисе сам автор «принципа нормализации:

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

А опыт, подтверждающий принцип нормализации, огромен. Ведь математикой люди занимаются довольно долго – не менее 4000 лет. За это время было придумано немало различных алгорифмов. И среди них не известно ни одного ненормализуемого. Как-никак, а это веский довод в пользу принципа нормализации. Не менее веский, чем, скажем, опытное подтверждение закона сохранения энергии»^[20].

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

Так к началу 50-х годов нашего века, то есть к моменту выхода на сцену электронных вычислительных машин, как итог развития всей предшествующей математики и логики и как непосредственный результат работ Чёрча, Тьюринга и Маркова, стал вырисовываться обширный комплекс процессов, обладающих следующими особенностями.

1. Они в принципе строго детерминированы, то есть каждый предыдущий этап полностью определяет последующий.

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

3. Они имеют «атомарное» строение – складываются из совокупности элементарных операций, которых имеется всего несколько видов.

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

А существуют ли в мире другие процессы?

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

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