Krasdiag [N] = 1 + Krasprogram {#N}[N]
Точно так же, как в случае с функцией Белдиаг, мы должны заключить, что Krasdiag [N] — хорошо определенная, вычисляемая функция одной переменной, которая не находится в списке Красных Программ и, следовательно, ее невозможно вычислить даже с помощью мощного языка Флуп. Не пора ли нам перейти к Глупу?
Глуп — …
Что же такое Глуп? если Флуп — это освобожденный от цепей Блуп, то Глуп должен, в свою очередь, быть освобожденным от цепей Флупом. Но как же можно снять цепи дважды? Как можно создать язык, более мощный, чем Флуп? Krasdiag [N] оказалась функцией, значение которой умеем вычислять только мы, люди, поскольку мы подробно описали всю процедуру на русском языке — однако эту функцию, по-видимому, невозможно запрограммировать на языке Флуп. Это — весьма серьезная проблема, поскольку никто пока не нашел компьютерного языка, более мощного, чем Флуп.
Мощность компьютерных языков в последнее время была объектом тщательных исследований. Нам самим не придется этим заниматься; упомянем только, что существует целый класс компьютерных программ с точно такой же выразительной мощностью, как Флуп, в том смысле, что любое вычисление, программируемое на одном языке, может быть запрограммировано на всех остальных языках. Интересно то, что почти любая попытка создать достойный внимания компьютерный язык приводит к созданию языка этого класса, то есть языка с выразительной мощностью Флупа. Приходится попотеть, чтобы создать достаточно интересный компьютерный язык слабее этих языков. Блуп, разумеется, пример более слабого языка, но это — скорее исключение, чем правило. Дело в том, что существует некий естественный путь создания алгоритмических языков, так что разные люди, работая независимо друг от друга, обычно создают эквивалентные языки, отличающиеся скорее стилем, чем степенью мощности.
… ни что иное как миф
В действительности, большинство специалистов считают, что для описания вычислений не может существовать более мощных языков, чем языки, эквивалентные Флупу. Эта гипотеза была сформулирована в 1930-х годах двумя людьми, работавшими независимо друг от друга. Об одном из них, Алане Тьюринге, мы еще будем говорить; другим был один из ведущих логиков этого столетия, Алонзо Чёрч. Гипотеза получила название Тезис Чёрча-Тьюринга. Принимаем Тезис Ч-Т за истину, мы должны заключить, что Глуп — не более, чем миф, поскольку во Флупе нет никаких ограничений, которые можно было бы снять; его мощность невозможно усилить, «сняв с него цепи», как мы это сделали с Блупом.
Это ставит нас в неудобное положение: нам приходится заключить, что люди могут вычислить Krasdiag [N] для любого N, в то время как компьютер этого сделать не может. Дело в том что если бы это было в принципе возможно, это было бы возможно на Флупе — однако мы только что выяснили, что на Флупе этого нельзя сделать по определению. Это такое странное заключение, что нам придется как следует рассмотреть, на чем оно основано. Одним из краеугольных камней нашего построения было, если вы помните, сомнительное предположение о существовании разрешающей процедуры, способной отличить заканчивающиеся программы Флупа от незаканчивающихся. Возможность такой процедуры показалась подозрительной уже тогда, когда мы увидели, что она помогла бы разрешить все проблемы теории чисел одинаковым путем. Теперь у нас есть две причины, чтобы считать тест на кончаемость мифом; видимо, невозможно, пропустив программы Флупа через центрифугу, отличить терминаторы от не-терминаторов.
Скептики могут возразить: а где же строгое доказательство невозможности подобного теста? Это возражение имеет смысл. Однако в подходе Тюринга мы находим более строгое обоснование того, что на языке класса Флупа невозможно написать программу, проверяющую программы Флупа на кончаемость.
Тезис Чёрча-Тьюринга
Посмотрим, что представляет из себя этот Тезис. Мы будем говорить о нем во всех подробностях в главе XVII; до тех пор мы воздержимся от его обсуждения, а здесь дадим лишь пару версий Тезиса. Далее следуют три родственных способа его выражения:
(1) То, что могут вычислить люди, могут вычислить и машины.
(2) То, что могут вычислить машины, может быть вычислено с помощью Флупа.
(3) То, что могут вычислить люди, может быть вычислено с помощью Флупа.
Терминология: общерекурсивный и частично рекурсивный
В этой главе мы дали довольно широкий обзор некоторых понятий теории чисел и их соотношения с вычисляемыми функциями. Это очень плодотворное поле для исследований, поле, где переплетается теория вычислительной техники и современная математика. Прежде, чем заключить эту главу, я хочу ввести стандартные термины для понятий, с которыми мы здесь познакомились.
Как я уже говорил, выражение «вычислимый на Блупе» эквивалентно выражению «примитивно-рекурсивный». С другой стороны, функции, вычислимые на Флупе, можно подразделить на две категории. Функции, вычислимые с помощью кончающихся программ Флупа, называются общерекурсивными; функции, вычислимые только с помощью не кончающихся программ Флупа, называются частично рекурсивными. (То же самое применимо и к предикатам.) Многие, говоря о «рекурсивных» функциях, на самом деле имеют в виду их «общерекурсивную» разновидность.
Мощь ТТЧ
Интересно, что ТТЧ настолько мощна, что в ней представлены не только все примитивно-рекурсивные предикаты, но и все общерекурсивные предикаты. Мы не будем приводить здесь доказательство обоих фактов, поскольку это увело бы нас в сторону от нашей цели — показать, что ТТЧ неполна. Если бы ТТЧ не могла выразить какие-либо примитивно-рекурсивные или общерекурсивные предикаты, ее неполнота была бы неинтересна — так почему бы нам не согласиться с тем, что все эти предикаты в ней выразимы, и не доказать, что она неполна в другом, более интересном смысле?
Черепаха и Ахилл возвращаются с экскурсии по фабрике консервных ключей.
Ахилл: Вы не возражаете, если я поменяю тему?
Черепаха: Ради Бога.
Ахилл: Хорошо. Я хотел вам рассказать, что несколько дней тому назад меня разбудил хулиганский телефонный звонок.
Черепаха: Как интересно!
Ахилл: Да уж… Дело в том, что нахал сказал что-то совершенно бессмысленное. Он крикнул мне в ухо какую-то идиотскую фразу и повесил трубку… хотя, кажется, прежде чем повесить трубку, он повторил эту бессмыслицу дважды.
Черепаха: Вы помните, что именно он сказал?
Ахилл: Наш разговор проходил так:
Я: Алло?
Таинственный голос (дико орет): Предваренное цитатой себя самого, порождает ложь! Предваренное цитатой себя самого, порождает ложь!
(Щелчок. Короткие гудки)
Черепаха: Для хулиганского звонка это довольно необычно.
Ахилл: Вот и я так подумал.
Черепаха: Может быть, в этой кажущейся чепухе все же есть какой-то смысл.
Ахилл: Кто знает…
(Они входят в небольшой дворик, окруженный прелестными трехэтажными домами. В центре двора растет пальма; сбоку стоит башня. Около башни — ступеньки, на которых сидит мальчик, занятый беседой с девушкой в окне.)
Черепаха: Куда это вы меня привели, Ахилл?
Ахилл: Я хочу показать вам замечательный вид, открывающийся с этой башни.
Черепаха: Ах, как мило!
(Они приближаются к мальчику, который смотрит на них с любопытством и говорит что-то девушке; оба хихикают. Вместо того, чтобы подниматься по лестнице, где сидит мальчишка, Ахилл и г-жа Ч поворачивают налево и спускаются по ступенькам, ведущим к небольшой деревянной двери.)
Ахилл: Вот и вход. Следуйте за мной.
(Ахилл открывает дверь. Они входят и начинают подниматься по крутой винтовой лесенке.)
Черепаха (сопя и отдуваясь): Я не гожусь для таких упражнений, Ахилл. Еще далеко?
Ахилл: Несколько пролетов… но у меня есть идея. Вместо того, чтобы карабкаться по верхней стороне лестницы, почему бы вам не попробовать идти по нижней стороне?
Рис. 74. М. К. Эшер. «Сверху и снизу» (литография, 1947).
Черепаха: Как же ТАКОЕ возможно?
Ахилл: Запросто, держитесь покрепче и переползайте на обратную сторону ступеней — места там достаточно. Вы увидите, что по этой лестнице можно ходить так же хорошо снизу, как и сверху…
Черепаха (переползая на обратную сторону ступенек): Ну как, правильно?
