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