Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

Мы определили примитивно-рекурсивные функции и примитивно-рекурсивные свойства натуральных чисел с помощью программ, написанных на языке Блуп. Мы также показали, что Блуп не описывает всех функций натуральных чисел, которые можно выразить словами. Мы даже построили, пользуясь Канторовским методом, «не-Блупабельную» функцию Beldiag [N]. Что же именно в Блупе делает невозможным представить в нем функцию Beldiag [N]? Можно ли улучшить Блуп таким образом, что Beldiag [N] станет в нем представимой?

Определяющей чертой Блупа была ограниченность его циклов. Что, если мы опустим это требование и создадим второй язык, под названием Флуп? Флуп будет идентичен Блупу во всем, кроме одного: в нем можно будет иметь циклы как с потолком, так и без потолка (на самом деле, потолок здесь будет включаться в циклы исключительно для элегантности). Эти новые циклы будут называться MU-циклы, следуя обозначению, принятому в математической логике, где «свободный (неограниченный) поиск» обычно обозначается символом «μ — оператор». Таким образом, цикл в Флупе может выглядеть так:

MU-ЦИКЛ:

БЛОК n: НАЧАЛО

.

.

.

БЛОК n: КОНЕЦ

Эта характеристика позволит нам написать на Флупе тесты для свойства Черепахи и свойства интересности — тесты, которые мы не могли создать на Блупе из-за того, что поиск там мог оказаться потенциально бесконечным. Интересующиеся читатели могут попробовать написать на Флупе следующий тест на интересности:

(1) Если вводной параметр N оказывается интересным числом, программа останавливается и выдает ответ ДА.

(2) Если N — неинтересное число, порождающее любой закрытый цикл, отличный от 1-4-2-1-4-2-1-…, программа останавливается и выдает ответ НЕТ.

(3) Если N — неинтересное число, порождающее «бесконечно возрастающую прогрессию», программа никогда не останавливается. Это «не-отвечание» и есть ответ Флупа. He-ответ Флупа странным образом напоминает не-ответ Джошу — «МУ».

Ирония (3) заключается в том, что ВЫХОД всегда принимает значение НЕТ, но при этом он недоступен, поскольку программа все еще работает. Неприятная третья альтернатива — это та цена, которую нам приходится платить за право писать свободные циклы. Незаконченность всегда будет теоретической альтернативой для всех программ Флупа, включающих вариант MU-цикла. Разумеется, множество программ Флупа будут заканчиваться для всех возможных величин вводного параметра. Например, как я уже говорил, большинство людей, изучавших свойство интересности, считают, что программы Флупа, подобные описанной выше, всегда будут заканчиваться — и, более того, всегда ответом ДА.

Было бы очень хорошо, если бы нам удалось разделить все процедуры Флупа на два класса: оканчивающиеся (терминаторы) и неоканчивающиеся (не-терминаторы). Первые всегда будут рано или поздно останавливаться, независимо от входных параметров и от наличия в нем MU-циклов. Вторые будут работать до бесконечности по крайней мере при одном из возможных выборов входного параметра. Если бы всегда можно было, внимательно рассмотрев данную программу Флупа, определить к какому типу она принадлежит, это привело бы к важным последствиям (как мы скоро увидим). Нет нужды говорить, что сама операция определения классов должна была 6ы принадлежать к оканчивающемуся типу, иначе бы от нее было мало пользы.

Может быть, нам удастся заставить какую-нибудь из процедур самого Флупа заняться этой проверкой? Загвоздка здесь в том, что процедуры Флупа принимают в качестве вводных параметров только числа, а не программы. Однако это препятствие можно обойти … закодировав программы с помощью чисел! Этот ловкий трюк — не что иное, как Гёделева нумерация в одной из многих своих манифестаций. Каждый из 88 символов алфавита Флупа получит свой «кодон»: 901, 902, …988. Таким образом, каждая программа Флупа приобретает некий длинный Гёделев номер. Например, самая короткая функция Блупа (которая в то же время является оканчивающейся программой Флупа)

ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «А» [В]:

БЛОК 0:НАЧАЛО

БЛОК 0: КОНЕЦ.

получит Гёделев номер, частично показанный ниже:

915,916,917,906,905,906,912,909,919,929,....... 911, 915,914,906,923,987

О П Р Е Д Е Л И Т Ь К О Н Е Ц .

Теперь нам нужен тест Блупа под названием ТЕРМИНАТОР?, который отвечал бы ДА, если входной параметр являлся бы кодом оканчивающейся программы Флупа, и НЕТ — в противном случае. Таким образом, если нам повезет, мы сможем заставить машину отличать терминаторы от не-терминаторов. Однако хитроумный аргумент, придуманный Аланом Тьюрингом, доказал, что никакая программа Блупа не сможет безошибочно находить это различие. Его идея весьма напоминает Гёделев метод и, таким образом, находится в близком родстве с диагональным методом Кантора. Не буду приводить ее здесь; достаточно сказать, что идея Тьюринга заключалась в том, чтобы ввести в программу ее собственный Гёделев номер. Это, однако, весьма непросто, все равно что ухитриться процитировать какое-то предложение внутри него самого. Для этого пришлось бы процитировать также и саму цитату… и так далее, и тому подобное. Очевидно, что это приводит к бесконечному регрессу. Однако Тьюринг придумал ловкий трюк, позволяющий скормить программе ее собственный Гёделев номер. В следующей главе я приведу решение этой проблемы в ином контексте. Однако сейчас мы пойдем к той же цели другой дорогой — а именно, постараемся доказать, что такой тест невозможен. Читатели, которые хотят ознакомиться с элегантной и простой версией метода Тьюринга, могут обратиться к статье Хоара и Аллисона (Hoar and Allison), упоминающейся в библиографии.

Прежде, чем окончательно распроститься с этим понятием, давайте посмотрим, почему иметь такую программу было бы так замечательно. Такой тест был бы чем-то вроде волшебной палочки, которая могла бы одним взмахом разрешить все проблемы теории чисел. Предположим, мы захотели бы узнать, является ли Вариация Гольдбаха истинным предположением — иными словами, все ли числа обладают свойством Черепахи. Для начала мы написали бы тест на Флупе под названием ЧЕРЕПАХА?, который проверял бы, есть ли у вводного параметра данное свойство. Дефект этой программы — то, что она не кончается, если ввод не обладает свойством Черепахи — здесь превращается в достоинство, поскольку теперь мы можем проверить процедуру ЧЕРЕПАХА? на ее кончаемость. Если наш тест отвечает ДА, это значит, что ЧЕРЕПАХА? кончается для всех вводных параметров — иными словами, все числа обладают свойством Черепахи. Ответ НЕТ означал бы, что имеется некое число, обладающее свойством Ахилла. Ирония заключается в том, что мы никогда не используем саму программу ЧЕРЕПАХА? — мы только ее проверяем.