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