.
БЛОК 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), упоминающейся в библиографии.
Программа-тест терминаторов была бы волшебной
Прежде, чем окончательно распроститься с этим понятием, давайте посмотрим, почему иметь такую программу было бы так замечательно. Такой тест был бы чем-то вроде волшебной палочки, которая могла бы одним взмахом разрешить все проблемы теории чисел. Предположим, мы захотели бы узнать, является ли Вариация Гольдбаха истинным предположением — иными словами, все ли числа обладают свойством Черепахи. Для начала мы написали бы тест на Флупе под названием ЧЕРЕПАХА?, который проверял бы, есть ли у вводного параметра данное свойство. Дефект этой программы — то, что она не кончается, если ввод не обладает свойством Черепахи — здесь превращается в достоинство, поскольку теперь мы можем проверить процедуру ЧЕРЕПАХА? на ее кончаемость. Если наш тест отвечает ДА, это значит, что ЧЕРЕПАХА? кончается для всех вводных параметров — иными словами, все числа обладают свойством Черепахи. Ответ НЕТ означал бы, что имеется некое число, обладающее свойством Ахилла. Ирония заключается в том, что мы никогда не используем саму программу ЧЕРЕПАХА? — мы только ее проверяем.
Идея решения любой проблемы теории чисел путем кодирования ее в программу и затем проверки этой программы на кончаемость сродни идее о проверке подлинности буддистского коана путем кодирования его в сложенную цепочку и затем проверяя на наличие буддистской природы уже эту цепочку. Может быть, Ахилл был прав, предполагая, что нужная информация может лежать ближе к поверхности в одном отображении, чем в другом.
Клуб Ф, числа-индексы и Зеленые Программы
Довольно мечтать — пора заняться делом! Как можно доказать, что тест на кончаемость в принципе невозможен? Для этого мы попытаемся применить диагональный аргумент к Флупу, так же, как мы это делали с Блупом. Мы увидим, что между этими двумя случаями есть небольшая, но решающая разница.
Так же, как в случае Блупа, вообразим клуб, членами которого являются все программы Флупа. Мы будем называть его «Клубом Ф». Теперь проведем с ним те же три фильтрующих операции, после чего мы получим:
Полный клуб всех безвызовных программ Флупа, которые вычисляют функции с одним вводным параметром.
Давайте назовем эти специальные программы Флупа Зелеными Программами (поскольку они могут идти, никогда не останавливаясь, словно машины на зеленый свет).
Теперь, точно так же как мы это сделали с Белыми Программами, дадим каждой Зеленой Программе индекс и организуем их в каталог, каждый том которого состоит из программ определенной длины, расположенных в алфавитном порядке.
До сих пор мы просто повторяли с Флупом то, что ранее проделали с Блупом. Посмотрим теперь, удастся ли нам скопировать последнюю часть — диагональный метод. Попробуем определить диагональную функцию:
Zeldiag [N] = 1 + Zelprogram {#N}[N]
Тут получается заминка: функция Zeldiag [N] может не иметь определенного значения выхода для всех значений входного параметра N. Это происходит потому, что при «фильтровании» мы не очистили Клуб Ф от всех неоканчивающихся программ — таким образом, у нас нет гарантии, что мы сможем вычислить Zeldiag [N] для всех значений N. Иногда мы можем ввести вычисления, которые никогда не окончатся. Диагональный аргумент в этом случае не годится, так как для его успешного приложения диагональная функция должна иметь значение для всех возможных входных параметров.
Проверка на кончаемость и Красные Программы
Чтобы поправить положение, мы могли бы использовать тест на кончаемость — если бы таковой существовал. Давайте предположим на минуту, что такой тест имеется, и используем его в качестве нашего четвертого фильтра. Идя по списку Зеленых Программ, мы начинаем отбрасывать одну за другой все не-терминаторы, так что в конце у нас остается:
Полный клуб всех безвызовных программ Флупа, которые вычисляют функции с одним входным параметром и которые оканчиваются для всех его значений.
Давайте назовем эти специальные программы Флупа Красными Программами (поскольку они всегда должны останавливаться, как машины на красный свет). Теперь мы можем применить диагональный аргумент. Определим:
