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

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

Здесь мы наблюдаем действие живой «машины Тьюринга», описание которой исключительно просто. Обозначим обычное состояние кошки через С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].