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

Посмотрим, что представляет из себя этот Тезис. Мы будем говорить о нем во всех подробностях в главе XVII; до тех пор мы воздержимся от его обсуждения, а здесь дадим лишь пару версий Тезиса. Далее следуют три родственных способа его выражения:

(1) То, что могут вычислить люди, могут вычислить и машины.

(2) То, что могут вычислить машины, может быть вычислено с помощью Флупа.

(3) То, что могут вычислить люди, может быть вычислено с помощью Флупа.

В этой главе мы дали довольно широкий обзор некоторых понятий теории чисел и их соотношения с вычисляемыми функциями. Это очень плодотворное поле для исследований, поле, где переплетается теория вычислительной техники и современная математика. Прежде, чем заключить эту главу, я хочу ввести стандартные термины для понятий, с которыми мы здесь познакомились.

Как я уже говорил, выражение «вычислимый на Блупе» эквивалентно выражению «примитивно-рекурсивный». С другой стороны, функции, вычислимые на Флупе, можно подразделить на две категории. Функции, вычислимые с помощью кончающихся программ Флупа, называются общерекурсивными ; функции, вычислимые только с помощью не кончающихся программ Флупа, называются частично рекурсивными . (То же самое применимо и к предикатам.) Многие, говоря о «рекурсивных» функциях, на самом деле имеют в виду их «общерекурсивную» разновидность.

Интересно, что ТТЧ настолько мощна, что в ней представлены не только все примитивно-рекурсивные предикаты, но и все общерекурсивные предикаты. Мы не будем приводить здесь доказательство обоих фактов, поскольку это увело бы нас в сторону от нашей цели — показать, что ТТЧ неполна. Если бы ТТЧ не могла выразить какие-либо примитивно-рекурсивные или общерекурсивные предикаты, ее неполнота была бы неинтересна — так почему бы нам не согласиться с тем, что все эти предикаты в ней выразимы, и не доказать, что она неполна в другом, более интересном смысле?

Черепаха и Ахилл возвращаются с экскурсии по фабрике консервных ключей.

Ахилл : Вы не возражаете, если я поменяю тему?

Черепаха : Ради Бога.

Ахилл : Хорошо. Я хотел вам рассказать, что несколько дней тому назад меня разбудил хулиганский телефонный звонок.

Черепаха : Как интересно!

Ахилл : Да уж… Дело в том, что нахал сказал что-то совершенно бессмысленное. Он крикнул мне в ухо какую-то идиотскую фразу и повесил трубку… хотя, кажется, прежде чем повесить трубку, он повторил эту бессмыслицу дважды.

Черепаха : Вы помните, что именно он сказал?

Ахилл : Наш разговор проходил так:

Я: Алло?

Таинственный голос (дико орет): Предваренное цитатой себя самого, порождает ложь! Предваренное цитатой себя самого, порождает ложь!

(Щелчок. Короткие гудки)

Черепаха : Для хулиганского звонка это довольно необычно.

Ахилл : Вот и я так подумал.

Черепаха : Может быть, в этой кажущейся чепухе все же есть какой-то смысл.

Ахилл: Кто знает…

(Они входят в небольшой дворик, окруженный прелестными трехэтажными домами. В центре двора растет пальма; сбоку стоит башня. Около башни — ступеньки, на которых сидит мальчик, занятый беседой с девушкой в окне.)

Черепаха : Куда это вы меня привели, Ахилл?

Ахилл : Я хочу показать вам замечательный вид, открывающийся с этой башни.

Черепаха : Ах, как мило!

(Они приближаются к мальчику, который смотрит на них с любопытством и говорит что-то девушке; оба хихикают. Вместо того, чтобы подниматься по лестнице, где сидит мальчишка, Ахилл и г-жа Ч поворачивают налево и спускаются по ступенькам, ведущим к небольшой деревянной двери.)

Ахилл : Вот и вход. Следуйте за мной.

(Ахилл открывает дверь. Они входят и начинают подниматься по крутой винтовой лесенке.)

Черепаха (сопя и отдуваясь) : Я не гожусь для таких упражнений, Ахилл. Еще далеко?

Ахилл : Несколько пролетов… но у меня есть идея. Вместо того, чтобы карабкаться по верхней стороне лестницы, почему бы вам не попробовать идти по нижней стороне?

Рис. 74. М. К. Эшер. «Сверху и снизу» (литография, 1947).

Черепаха : Как же ТАКОЕ возможно?

Ахилл : Запросто, держитесь покрепче и переползайте на обратную сторону ступеней — места там достаточно. Вы увидите, что по этой лестнице можно ходить так же хорошо снизу, как и сверху…

Черепаха (переползая на обратную сторону ступенек) : Ну как, правильно?

Ахилл : Все верно, молодец!

Черепаха (слегка приглушенным голосом) : Это упражнение меня слегка запутало. Куда мне теперь идти — вверх или вниз?

Ахилл : Держитесь того же направления, как раньше. На вашей стороне ступенек это будет ВНИЗ, а на моей — ВВЕРХ.

Черепаха : Надеюсь, вы не хотите сказать, что спускаясь по лестнице, я могу попасть на вершину башни?

Ахилл : Почему-то получается именно так.

(И они начинают карабкаться по лестнице, одновременно описывая спирали — Атлетический Ахилл на одной стороне, и Тяжеловесная Черепаха Тортилла на другой. Вскоре лестница кончается)

Теперь вылезайте обратно, г-жа Черепаха. Дайте-ка я вам помогу.

(Он подает Черепахе руку и помогает ей забраться на верхнюю сторону ступенек)

Черепаха : Спасибо. Залезть обратно наверх было полегче.

(И они выходят на крышу, откуда открывается вид на город)

Какая красота, Ахилл. Я рада, что вы привели меня наверх — или, скорее, ВНИЗ.

Ахилл : Я так и знал, что вам понравится.

Черепаха : Знаете, возвращаясь к тому хулиганскому звонку, — мне кажется, теперь я лучше понимаю, в чем дело.

Ахилл : Да? Надеюсь, вы со мной поделитесь.

Черепаха : С удовольствием. Вам не кажется, что выражение «предваряемый цитатой самого себя» звучит немного рекурсивно?

Ахилл : Да. Немного Самую малость…

Черепаха : Можете ли вы вообразить себе что-либо, предваряемое собственной цитатой?

Ахилл : Пожалуй, например, Мао, входящий в банкетный зал, где уже повешен плакат с каким-либо его изречением. Получается Мао, предваряемый цитатой самого себя.

Черепаха : Какое у вас богатое воображение. Но давайте договоримся, что слово «предваряемый» будет относиться только к идее предварения на листе бумаги, а не к цитатам из государственных мужей.

Ахилл : Ну ладно. Но тогда заодно скажите, что вы имеете в виду под «цитатой»?

Черепаха : Когда вы говорите о каком-то слове или фразе, вы обычно заключаете их в кавычки. Например, я могу сказать: