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

Автор книги: Даглас Хофштадтер

сообщить о нарушении

Текущая страница: 38 (всего у книги 64 страниц)

… ни что иное как миф

В действительности, большинство специалистов считают, что для описания вычислений не может существовать более мощных языков, чем языки, эквивалентные Флупу. Эта гипотеза была сформулирована в 1930-х годах двумя людьми, работавшими независимо друг от друга. Об одном из них, Алане Тьюринге, мы еще будем говорить; другим был один из ведущих логиков этого столетия, Алонзо Чёрч. Гипотеза получила название Тезис Чёрча-Тьюринга. Принимаем Тезис Ч-Т за истину, мы должны заключить, что Глуп – не более, чем миф, поскольку во Флупе нет никаких ограничений, которые можно было бы снять; его мощность невозможно усилить, «сняв с него цепи», как мы это сделали с Блупом.

Это ставит нас в неудобное положение: нам приходится заключить, что люди могут вычислить Krasdiag [N] для любого N, в то время как компьютер этого сделать не может. Дело в том что если бы это было в принципе возможно, это было бы возможно на Флупе – однако мы только что выяснили, что на Флупе этого нельзя сделать по определению. Это такое странное заключение, что нам придется как следует рассмотреть, на чем оно основано. Одним из краеугольных камней нашего построения было, если вы помните, сомнительное предположение о существовании разрешающей процедуры, способной отличить заканчивающиеся программы Флупа от незаканчивающихся. Возможность такой процедуры показалась подозрительной уже тогда, когда мы увидели, что она помогла бы разрешить все проблемы теории чисел одинаковым путем. Теперь у нас есть две причины, чтобы считать тест на кончаемость мифом; видимо, невозможно, пропустив программы Флупа через центрифугу, отличить терминаторы от не-терминаторов.

Скептики могут возразить: а где же строгое доказательство невозможности подобного теста? Это возражение имеет смысл. Однако в подходе Тюринга мы находим более строгое обоснование того, что на языке класса Флупа невозможно написать программу, проверяющую программы Флупа на кончаемость.

Тезис Чёрча-Тьюринга

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

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

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

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

Терминология: общерекурсивный и частично рекурсивный

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

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

Мощь ТТЧ

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

Ария в ключе G

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

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

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

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

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

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

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

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

Я: Алло?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В слове «философ» пять букв.

Я поставила «философ» в кавычки, чтобы указать, что я имею в виду СЛОВО «философ», а не философа собственной персоной. Это пример различия между «ИСПОЛЬЗОВАНИЕМ» и «УПОМИНАНИЕМ».

Ахилл: Что?

Черепаха: Позвольте мне объяснить. Когда я говорю:

Философы зарабатывают кучу денег, —

я ИСПОЛЬЗУЮ слово, чтобы создать у вас в голове образ седобородого мудреца, окруженного мешками денег. Но заключая это – или любое другое – слово в кавычки, я тем самым лишаю его собственного значения и набора связанных с ним ассоциаций, и у меня остаются только значки на бумаге или звуки. Это называется «УПОМИНАНИЕ». При этом важен только типографский аспект слова, а его значение полностью игнорируется.

Ахилл: Это похоже на использование скрипки в качестве мухобойки. Или, может быть, точнее было бы сказать «упоминание скрипки»? Тут в скрипке важна только ее твердость – любое другое ее значение и возможное использование полностью игнорируются. Если подумать, то при этом мы обходимся ничуть не лучше и с мухой.

Черепаха: Ваши сравнения не лишены смысла, хотя они и являются весьма нестандартной интерпретацией различия между ИСПОЛЬЗОВАНИЕМ и УПОМИНАНИЕМ. Теперь, пожалуйста, представьте что-либо, предваряемое собственной цитатой.

Ахилл: Ну что ж… Как насчет:

«ГИП-ГИП УРА» ГИП-ГИП УРА

Черепаха: Здорово! А еще что-нибудь?

Ахилл: Ладно:

«„ПЛЮХ“ – ЭТО НЕ НАЗВАНИЕ КНИГИ»

«ПЛЮХ» – ЭТО НЕ НАЗВАНИЕ КНИГИ.

Черепаха: Этот пример станет гораздо интереснее, если убрать из него «Плюх».

Ахилл: Правда? Посмотрим:

«ЭТО НЕ НАЗВАНИЕ КНИГИ»

ЭТО НЕ НАЗВАНИЕ КНИГИ.

Черепаха: Видите, у вас получилось предложение.

Ахилл: И правда! Это предложение о фразе «это не название книги» – и предложение преглупое.

Черепаха: Почему преглупое?

Ахилл: Потому, что оно совершенно бессмысленно. Вот вам еще одно в том же духе:

«ЗАВИСИТ ОТ ТОГО, СКОЛЬКО ДЕНЕГ У КОГО»

ЗАВИСИТ ОТ ТОГО, СКОЛЬКО ДЕНЕГ У КОГО.

Ну, и что это означает? Право слово, что за глупая игра.

Черепаха: Ну что вы – напротив, это очень серьезно. В действительности, эта операция предварения некоей фразы ее собственной цитатой настолько важна, что я дам ей специальное имя.

Ахилл: Да? Какого же названия удостоится эта глупая операция?

Черепаха: Думаю, что я назову это «квайнированием» фразы.

Ахилл: «Квайнирование»? Что это еще за слово?

Черепаха: Если не ошибаюсь, это слово из тринадцати букв.

Ахилл: Я имел в виду, почему вы выбрали именно эти тринадцать букв и именно в таком порядке.

Черепаха: Ага, теперь я понимаю, что вы хотели сказать, спросив меня: «Что это еще за слово?» Видите ли, эту операцию изобрел философ по имени «Виллард Ван Орман Квайн», так что я назвал ее в его честь. К сожалению, подробнее объяснить не могу. Почему его имя состоит именно из этих букв, и именно в таком порядке – на этот вопрос у меня пока нет ответа. Но я готова попытаться —

Ахилл: Прошу вас, не утруждайтесь! Меня совсем не интересуют эти детали. Так или иначе, теперь я умею квайнировать фразы. Это довольно занимательно… Вот еще одна квайнированная фраза:

«ЭТО ФРАГМЕНТ ПРЕДЛОЖЕНИЯ» ЭТО ФРАГМЕНТ ПРЕДЛОЖЕНИЯ.

Разумеется, это глупо, зато интересно. Вы берете кусочек предложения, квайнируете его, и оп-ля! перед вами что-то новое! В данном случае, это настоящее предложение.

Черепаха: Попробуйте квайнировать фразу «это фуга без темы».

Ахилл: Фуга без темы была бы —

Черепаха: – аномалией, разумеется. Но не отвлекайтесь. Сначала квайны, а потом пьесы. Как говорится, сделал дело – играй смело!

Ахилл: Квайны, говорите? Хорошо:

«ЭТО ФУГА БЕЗ ТЕМЫ» ЭТО ФУГА БЕЗ ТЕМЫ

Мне кажется, что больше смысла было бы говорить о «предложении» вместо «фуги». Ну да ладно… Дайте мне еще пример!

Черепаха: Хорошо, вот вам напоследок такая фраза:

«ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ».

Ахилл: Это совсем нетрудно:

«ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ».

ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ.

Гмм… Что-то здесь не то. О, понятно – это предложение говорит о себе самом! Видите?

Черепаха: Что вы хотите сказать? Предложения не умеют говорить.

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

Черепаха: Мне совсем не кажется, что это предложение говорит о себе самом. Покажите мне хотя бы одно «Я», или «это предложение», или что-нибудь в этом роде.

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

Черепаха: Придется вам разложить это для меня по полочкам – я женщина простая и таких сложностей не понимаю.

Ахилл: Вы ведете себя как Фома Неверующий. Ну ладно, постараюсь… Представьте себе, что я придумываю предложение – назовем его «предложением П» – и оставляю в нем прочерк.

Черепаха: Например?

Ахилл: Вот так:

« ___ ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ».

Теперь тема предложения П зависит от того, как вы заполните прочерк. Как только вы сделали выбор, тема определена: Это будет фраза, которую вы получите, кзайнировав то, что оказалось на месте прочерка. Назовем это «предложением К», поскольку оно получается в результате квайнирования.

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

«НАПИСАНО НА СТАРЫХ БАНКАХ ГОРЧИЦЫ, ЧТОБЫ СОХРАНЯТЬ ЕЕ СВЕЖЕЙ»

НАПИСАНО НА СТАРЫХ БАНКАХ ГОРЧИЦЫ, ЧТОБЫ СОХРАНЯТЬ ЕЕ СВЕЖЕЙ.

Ахилл: Значит, Предложение П утверждает (не знаю, правда, насколько это верно), что Предложение К – Любовная Песнь Черепахи. Так или иначе, Предложение П здесь говорит не о себе самом, но о Предложении К. Согласны ли вы с этим?

Черепаха: Безусловно – и что за прелестная Песнь!

Ахилл: Но теперь я хочу заполнить прочерк чем-то другим, а именно:

«ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ».

Черепаха: Ах, боже мой! Вы слишком все усложняете. Боюсь, этот орешек окажется мне не по зубам…

Ахилл: О, не волнуйтесь – я уверен, что скоро вы все поймете. Теперь Предложением К становится:

«ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ»

ПОСЛЕ КВАЙНИРОВАНИЯ ДАЕТ ЛЮБОВНУЮ ПЕСНЬ ЧЕРЕПАХИ.

Черепаха: Постойте-ка, я, кажется, поняла! Предложение К теперь стало совершенно таким же, как и предложение П.

Ахилл: И, поскольку Предложение К – всегда тема предложения П, у нас получается петля: Предложение П теперь указывает на самого себя. Как видите, автореферентность здесь получилась вполне случайно. Обычно Предложения П и К совершенно не похожи – но при правильном выборе темы в предложении П, квайнирование покажет вам этот магический трюк.

Черепаха: Ловко, ничего не скажешь! Странно, почему я сама до этого не додумалась. Скажите, а следующее предложение тоже автореферентно?

«СОСТОИТ ИЗ ЧЕТЫРЕХ СЛОВ»

СОСТОИТ ИЗ ЧЕТЫРЕХ СЛОВ.

Ахилл: Гм-м… Трудно сказать. Это предложение относится не себе самому, но скорее ко фразе «состоит из четырех слов». Хотя, разумеется, эта фраза – ЧАСТЬ предложения.

Черепаха: Так что предложение говорит о своей части – и что же?

Ахилл: Это можно тоже рассматривать как автореференцию, не так ли?

Черепаха: По моему мнению, отсюда еще далеко до настоящей автореферентности. Но не забивайте себе сейчас голову этими сложностями – у вас еще будет время о них поразмыслить.

Ахилл: Правда?

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

Ахилл: А, вы имеете в виду тот хулиганский звонок. Квайнирование этой фразы дает:

«ПРЕДВАРЯЕМЫЙ ЦИТАТОЙ СЕБЯ САМОГО, ПРОИЗВОДИТ ЛОЖЬ»

ПРЕДВАРЯЕМЫЙ ЦИТАТОЙ СЕБЯ САМОГО, ПРОИЗВОДИТ ЛОЖЬ.

Так вот что говорил тот негодяй! Я тогда его не понял. И правда, какое неприличное замечание! Да за такое надо в тюрьму сажать!

Черепаха: Это почему же?

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

Черепаха: Кто знает… Ну что, пора спускаться?

Ахилл: В этом нет нужды – мы уже на первом этаже. Зайдите обратно, и вы в этом убедитесь (Они заходят в башню и видят небольшую деревянную дверь) Вот и выход – следуйте за мной.

Черепаха: Вы уверены? Я вовсе не хочу свалиться с третьего этажа и сломать себе панцирь.

Ахилл: Разве я вас когда-нибудь обманывал?

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

Благодарю вас, г-жа Ч, за ваше объяснение по поводу того хулиганского звонка.

Черепаха: А я вас – за прелестную прогулку. Надеюсь, мы скоро увидимся опять.

ГЛАВА XIV: О формально неразрешимых суждениях ТТЧ и родственных систем[41]41
  Заглавие статьи Гёделя включало в конце римское I; это означало, что он собирался написать продолжение этой статьи с тем, чтобы подробно остановиться на особенно трудных моментах доказательства. Однако первая статья получила настолько широкое признание, что нужда в продолжении отпала, и вторая статья так и не была написана.


[Закрыть]

Две идеи «устрицы»

НАЗВАНИЕ ЭТОЙ ГЛАВЫ – адаптация заглавия знаменитой статьи Гёделя, опубликованной в 1931 году; я заменил «Principia mathematica» на ТТЧ. Гёдель написал эту статью строго техническим языком, стараясь дать безупречное доказательство своей теоремы; в этой главе я постараюсь изложить его идеи более интуитивно. Сосредоточусь на двух идеях, лежащих в основе Гёделева доказательства. Первая идея – это открытие того факта, что некоторые строчки ТТЧ могут быть интерпретированы как суждения о других строчках ТТЧ; иными словами, ТТЧ оказалась языком, способным к самоанализу. Этот факт вытекает из Гёделевой нумерации. Вторая идея – это то, что данное свойство может быть сконцентрировано полностью в одной строке: в фокусе такой строки – она сама. Этот прием восходит, в принципе, к диагональному методу Кантора.

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

Первая идея: пары доказательства

Не откладывая дела в долгий ящик, приступим к рассмотрению самого доказательства. В IX главе мы уже объяснили довольно подробно идею Гёделева изоморфизма. Здесь мы постараемся описать математическое понятие, позволяющее нам перевести предложение типа «Строчка 0=0 – теорема ТТЧ» в высказывание теории чисел. Для этого мы воспользуемся парами доказательства. Пара доказательства – это пара натуральных чисел, соотносящихся между собой таким образом:

Два натуральных числа m и n (в данном порядке) являются парой доказательства в ТТЧ тогда и только тогда, если m – Гёделев номер такой деривации ТТЧ, последняя строчка которой имеет Гёделев номер n.

Аналогичное понятие существует и для системы MIU; пожалуй, интуитивно легче понять именно этот случай. Так что давайте на минуту оставим пары доказательства ТТЧ и обратимся к парам доказательства в системе MIU. Их определение почти такое же:

Два натуральных числа m и n (в данном порядке) являются парой доказательства в MIU тогда и только тогда, если m – Гёделев номер такой деривации MIU, последняя строчка которой имеет Гёделев номер n.

Давайте рассмотрим несколько примеров пар доказательства в системе MIU. Пусть m – 3131131111301, n = 301. Эти значения тип составляют пару доказательства, поскольку m – Гёделев номер следующей деривации MIU:

MI

MII

MIIII

MUI

где последняя строчка – MUI – имеет Гёделев номер 301, то есть n.

С другой стороны, при m = 31311311130, и n = 30 пары доказательства не получается. Чтобы понять, почему, рассмотрим деривацию, кодом которой должно было бы являться m:

MI

MII

MIII

MU

В этой предположительной деривации есть неверный шаг. Это – переход от второй к третьей строке: от MII к MIII. В системе MIU нет правила, которое позволяло бы подобный типографский шаг. Соответственно – и это очень важно – нет такого арифметического шага, который позволил бы вам перейти от 311 к 3111. Возможно, что, после того как вы прочли главу IX, это покажется вам тривиальным, но именно подобные наблюдения лежат в основе Гёделева изоморфизма. Все, что мы делаем в формальных системах, имеет свою параллель в арифметических действиях.

Так или иначе, величины m = 31311311130, и n = 30, безусловно, не являются парой доказательства MIU. Само по себе, это еще не означает, что 30 – не номер MIU. Могло бы найтись другое число, составляющее пару доказательства с 30. (На самом деле, мы уже выяснили ранее, что 30 – не теорема MIU. Следовательно, ни одно число не может составлять пару доказательства с 30.)

А как насчет пар доказательства в ТТЧ? Я приведу вам два параллельных примера, лишь один из которых является действительной парой доказательства. Можете ли вы определить, какой именно? (Кстати, именно здесь появляется кодон «611», функция которого – отделять Гёделевы номера последующих строк в деривации ТТЧ. В этом смысле, «611» служит в качестве знака препинания. В системе MIU эту роль выполняет начальное «3» каждой строки; там не нужна никакая дополнительная пунктуация.)

1) m = 626,262,636,223,123.262,111,666,611,223,123,666,111,666

    n = 123,666,111,666

(2) m = 626,262,636,223,123,262,111.666,611,223.333,262,636123,262,111,666

     n = 223,333,262,636,123.262,111,666

Легко обнаружить, какая из этих дериваций настоящая, переведя их в традиционную нотацию и произведя стандартный анализ. При этом выясняется:

(1) является ли предполагаемая деривация, кодом которой является m, «законной»;

(2) если это так, то совпадает ли последняя строка деривации со строчкой, кодом которой является n.

Шаг (2) тривиален; шаг (1) тоже довольно прямолинеен, поскольку для него не нужен бесконечный поиск и в нем не спрятаны никакие петли. Вспомните примеры из системы MIU и просто мысленно замените правила MIU и ее аксиому на правила и аксиомы ТГЧ. В обоих случаях алгоритм один и тот же:

Следить за деривацией, переходя от строчки к строчке.

Отмечать строчки, являющиеся аксиомами.

Для каждой строчки, НЕ являющейся аксиомой, проверять, следует ли она из предыдущих строчек предполагаемой деривации.

Если все не-аксиомы следуют по правилам вывода из предыдущих строчек, значит, перед вами – законная деривация; в противном случае, перед вами – фальшивка.

На каждой ступени здесь совершается ограниченное число вполне определенных действий.

Свойство «пара-доказательности» примитивно рекурсивно …

Я делаю такой упор на ограниченность петель потому, что, как вы могли догадаться, я собираюсь доказать

ОСНОВНОЙ ФАКТ 1: Свойство пара-доказательности – это примитивно рекурсивное свойство теории чисел; следовательно, оно может быть проверено на программе Блупа.

Необходимо отличать это свойство от его близкого теоретико-численного родственника: свойства числа-теоремы. Если мы говорим, что n – число-теорема, мы имеем в виду. что существует некое число m, такое, что оно составляет с n пару доказательства. (Кстати, это приложимо как к ТТЧ, так и к системе MIU; пожалуй, полезно иметь в виду обе системы, пользуясь MIU как прототипом.) Чтобы проверить, является ли n числом-теоремой, вам придется проверить всех потенциальных пара-доказательных «партнеров» m – и именно тут вы вполне можете запутаться в бесконечной петле. Невозможно определить, сколько вам придется искать, пока вы наткнетесь на число, составляющее пару доказательства с n. Эта проблема возникает во всех системах, сочетающих удлиняющие и укорачивающие правила; подобная комбинация сообщает системе некоторую непредсказуемость.

Нам может пригодиться сейчас пример Вариации Гольдбаха. Проверить является ли пара чисел (m, n) Черепашьей парой нетрудно; это значит, что как m так и n+m должны быть простыми числами. Эта проверка несложна, потому что свойство простоты – примитивно рекурсивно, то есть может быть обнаружено при помощи конечного теста. Но если мы хотим узнать, обладает ли n свойством Черепахи, тогда нам нужно ответить на вопрос «существует ли некое число m, формирующее вместе с n Черепашью пару?» Это снова уводит нас в область неведомого, в страну бесконечной MU-петельности.

… и, следовательно, представлено в ТТЧ

Таким образом, из Основного Факта 1 мы можем вывести

ОСНОВНОЙ ФАКТ 2: Свойство формировать пару доказательства может быть проверено на Блупе – следовательно, оно представлено в ТТЧ некоей формулой с двумя свободными переменными.

Как и ранее, мы не упоминаем точно, к какой именно системе относятся данные пары доказательств; оказывается, что это не столь важно, потому что оба Основных Факта действительны для любой формальной системы. Это – общее свойство формальных систем: мы всегда можем определить при помощи предсказуемо конечного теста, является ли данная последовательность строк доказательством, или нет. То же верно и для соответствующих арифметических понятий.

Мощь пар доказательства

Для конкретности предположим, что мы имеем дело с системой MIU. Вы, наверное, помните строчку, которую мы назвали МУМОН'ом. На одном из уровней эта строчка интерпретировалась как утверждение «MU – теорема системы MIU.» Можно показать, как МУМОН выражается в ТТЧ с помощью формулы, выражающей понятие пар доказательства в MIU. Давайте сократим эту формулу, в существовании которой нас уверяет Основной Факт 2, следующим образом:

ПАРА-ДОКАЗАТЕЛЬСТВА-MIU{а, а'}

Поскольку это – свойство двух чисел, оно представлено формулой с двумя свободными переменными. (В этой главе мы будем пользоваться строгой версией ТТЧ и нам надо будет различать между переменными а, а', а'' и т. д.) Чтобы сказать: «MU – теорема системы MIU», нам придется взять изоморфное высказывание «30 – число-теорема системы MIU» и перевести его в нотацию ТТЧ. Это несложно, если призвать на помощь наше условное сокращение (вспомните главу VIII, в которой, чтобы указать замену каждого а' на, символ числа, слева от этого символа мы писали «/а'»):

Eа: ПАРА-ДОКАЗАТЕЛЬСТВА-MIU{a,SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS0/a'}

Посчитайте С: их 30 штук. Заметьте, что это – закрытое высказывание ТТЧ, поскольку одна свободная переменная квантифицированна, а другая заменена на символ числа. То, что мы здесь проделали, весьма интересно. Благодаря Основному Факту 2 мы получили возможность говорить о парах доказательства: теперь мы выяснили, как мы можем говорить о числах-теоремах: для этого нужно всего лишь добавить в начале квантор существования! Более точным переводом данной выше строчки было бы «существует некое число а, которое составляет пару доказательства с 30 в качестве второго элемента».

Предположим, что мы захотели бы проделать нечто похожее в ТТЧ – например, выразить высказывание «0=0 – это теорема ТТЧ». Мы можем сократить существующую (согласно Основному Факту 2) формулу аналогичным образом (опять с двумя свободными переменными):

ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{а, а'}

(Эта сокращенная формула ТТЧ читается так: «Натуральные числа а и а' являются парой доказательства».) Следующим шагом является перевод нашего высказывания в теорию чисел, следуя модели МУМОН. Получается высказывание «существует некое число а, которое составляет пару доказательства с 666,111,666 в качестве второго элемента». Это выражается следующей формулой ТТЧ:

Ea:ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ{a, SSSSS … SSSSS0/а'}

.                                                         |________|

.                                 (Очень много S – целых 666,111.666!)

Это – закрытое высказывание ТТЧ. (Давайте назовем его Джошу – скоро узнаете, почему.) Мы убедились, что возможно говорить не только о примитивно рекурсивном понятии пар доказательства ТТЧ, но и о родственном, хотя и более сложном понятии чисел-теорем ТТЧ.

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

(1) 0=0 не является теоремой ТТЧ.

(2) ~0=0 – теорема ТТЧ.

(3) ~0=0 не является теоремой ТТЧ.

Каким образом решения отличаются от примеров, данных выше, и друг от друга? Вот еще несколько упражнений на перевод:

(4) ДЖОШУ – теорема ТТЧ. (Получившуюся строчку ТТЧ назовите МЕТА-ДЖОШУ.)

(5) МЕТА-ДЖОШУ – теорема ТТЧ. (Получившуюся строчку ТТЧ назовите МЕТА-МЕТА-ДЖОШУ.)

(6) МЕТА-МЕТА-ДЖОШУ – теорема ТТЧ.

(7) МЕТА-МЕТА-МЕТА-ДЖОШУ – теорема ТТЧ.

(и т. д., и т. п.)

Пример (5) показывает, что высказывания мета-мета-ТТЧ могут быть переведены в нотацию ТТЧ; пример (6) показывает то же самое для мета-мета-мета-ТТЧ, и т. д.

Важно помнить о разнице между выражением свойства, и его представлением. Например, свойство численно-теоремности ТТЧ выражено следующей формулой:

Eа: ПАРА-ДОКАЗАТЕЛЬСТВА-ТТЧ {а, а'}

Перевод: «а' – число-теорема ТТЧ». Однако у нас нет гарантии того, что эта формула действительно представляет данное понятие, поскольку у нас нет гарантии того, что это свойство примитивно рекурсивно – на самом деле, у нас есть некоторые основания полагать, что это не так! (Наши подозрения вполне обоснованы. Свойство являться числом-теоремой ТТЧ – НЕ примитивно рекурсивно, и такой формулы ТТЧ, которая могла бы его выразить, не существует!) С другой стороны, свойство являться парой доказательства, являясь примитивно рекурсивным, одновременно выразимо и представимо с помощью формулы, данной выше.

Замена подводит нас ко второй идее

Предыдущее обсуждение показало нам, как ТТЧ может «анализировать» понятие теоремности ТТЧ. Это – основа первой части доказательства. Перейдем теперь ко второй идее доказательства, путем развития понятия, позволяющего сконцентрировать этот «самоанализ» в одной единственной формуле. Для этого давайте посмотрим, что случается с Гёделевым номером какой-либо формулы, когда ее структура слегка меняется. Рассмотрим следующее изменение:

замена всех свободных переменных на определенные символы чисел.

Ниже, в левой колонке, даны два примера этой операции; в правой колонке показаны параллельные изменения в Гёделевых номерах.