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