14. Логическая машина Фергюссона

Через несколько месяцев после того, как была с блеском разрешена загадка банковского сейфа в Монте-Карло, Крейг и Мак-Каллох наконец-то навестили Фергюссона — их очень заинтересовала его логическая машина. Разговор скоро зашел о сущности доказуемости.

— Я расскажу вам интересную и весьма поучительную историю, — сказал Фергюссон. — На экзамене по геометрии одного студента попросили доказать теорему Пифагора. Он сдал свою работу преподавателю, но тот возвратил ее с пометкой: «Это не доказательство!» Молодой человек пошел к преподавателю и сказал: «Сэр, как вы можете утверждать, будто то, что я вам сдал, — не доказательство? За весь курс лекций вы ни разу не дали нам определения доказательства. Вы давали нам строгие определения таких геометрических понятий, как треугольник, квадрат, окружность, параллельность, перпендикулярность и т. д., однако никогда не привели нам точного определения того, что же вы называете доказательством. Как же теперь вы можете так уверенно заявлять, будто мое доказательство — вовсе не доказательство? Как вы можете доказать, что оно не является доказательством?»

— Блестяще! — воскликнул Крейг, захлопав в ладоши. — Этот юноша далеко пойдет. А что же ответил преподаватель?

— К сожалению, — усмехнулся Фергюссон, — преподаватель оказался сухим педантом без чувства юмора и воображения. Он снизил студенту оценку за непочтительность.

— Очень жаль, — с досадой сказал Крейг. — Окажись я на месте преподавателя, непременно поставил бы этому студенту высший балл.

— Разумеется, — согласился Фергюссон, — я бы поступил точно так же. Но вы же прекрасно знаете, как часто преподаватели, лишенные творческого начала, побаиваются способных студентов.

— Должен признаться, — сказал Мак-Каллох, — что на месте этого преподавателя я бы тоже не смог ответить на вопрос студента. Разумеется, я похвалил мы его за толково поставленный вопрос, но ответить на него я бы все-таки не смог. В самом деле, что такое доказательство? Когда я сталкиваюсь с правильным доказательством, я почему-то всегда понимаю, что оно правильно; когда мне попадаются слабые аргументы, я обычно могу их указать. Но если бы меня попросили дать строгое определение доказательства, я тоже оказался бы в весьма затруднительном положении.

— Точно так же, как и почти все работающие математики, — поддержал Мак-Каллоха Фергюссон. — В девяносто девяти процентах случаев они вполне могут распознать правильность доказательства или указать на слабые места в неправильном доказательстве, однако не и состоянии привести точное определение доказательства. Нас же, логиков, интересует прежде всего анализ самого понятия «доказательство» — ведь мы хотим определить его так же строго, как и любое другое математическое понятие.

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

— Важно, и по нескольким причинам, — ответил Фергюссон. — Но даже не будь этих причин, я все равно котел бы знать это определение ради самого определения. В истории математики часто случалось, что какие-то основные понятия, например понятие непрерывности, интуитивно понимались и осваивались еще задолго до того, как для них было введено строгое определение. Однако, получив четкое определение, данное понятие как бы переходит в новую категорию. Становится возможным установить связанные с ним факты, которые было бы очень трудно или вовсе невозможно открыть, не зная совершенно четко объема этого понятия. В этом смысле не является исключением и понятие «доказательство». Так, иногда случается, что в доказательстве используется какой-нибудь новый принцип — например аксиома выбора — и при этом часто возникает сомнение, является ли применение этого принципа законным. Так вот, строгое определение понятия «доказательство» позволяет точно указать, какие математические принципы можно использовать, а какие нельзя.

С другой стороны, особенно важно иметь точное определение доказательства тогда, когда нужно установить, что данное математическое утверждение недоказуемо в той или иной системе аксиом. Данная ситуация очень похожа на положение дел с построением при помощи циркуля и линейки в евклидовой геометрии: там, для того чтобы показать, что некое построение (например, трисекция угла, квадратура круга или удвоение куба[6]) невозможно, требуется обычно более критическое определение понятия «построение», чем для того, чтобы показать, например, что то или иное геометрическое построение с помощью циркуля и линейки действительно возможно. То же самое происходит и с доказуемостью: чтобы продемонстрировать, что данное утверждение недоказуемо в некоторой исходной системе аксиом, требуется гораздо более строгое и критическое определение самого понятия «доказательство», чем для получения соответствующего положительного результата, а именно что данное утверждение в самом деле является доказуемым при принятии той или иной аксиомы.

Загадка Гёделя

— Итак, — продолжал Фергюссон, — если задана некоторая система аксиом, то доказательство в данной системе представляет собой конечную последовательность высказываний, построенную по очень строгим правилам. При этом оказывается совсем несложно чисто механическим путем решить, является ли данная последовательность высказываний доказательством в этой системе или нет. Собственно говоря, совсем несложно даже придумать машину, которая может это делать. Гораздо труднее оказывается создать такую машину, которая могла бы решать, какие высказывания в данной системе аксиом доказуемы, а какие нет.

— Ответ, я полагаю, зависит от выбора исходной системы аксиом…

— Сейчас меня интересуют вопросы механического доказательства теорем, то есть вопросы создания таких машин, которые могли бы доказывать различные математические истины. Вот, например, мое последнее детище, — сказал Фергюссон, с гордостью указав на какое-то престранное сооружение.

Крейг и Мак-Каллох несколько минут разглядывали машину, пытаясь разгадать ее назначение.

— И что же она умеет? — спросил наконец Крейг.

— Она может доказывать различные утверждения, касающиеся положительных целых чисел, — ответил Фергюссон. — Я использую язык, в котором имеются имена для разных множеств чисел, — точнее, подмножеств положительных целых чисел. При этом существует бесконечно много таких числовых множеств, которые поддаются наименованию на этом языке. Например, у нас имеются специальные названия для множества четных чисел, для множества нечетных чисел, для множества простых чисел, для множества чисел, делящихся на 3, и т. д. — вообще, можно сказать, что практически любое множество чисел, которое могло бы представить интерес для специалиста по теории чисел, обладает своим именем на этом языке. И хотя сама совокупность числовых множеств, поддающихся описанию на этом языке, содержит бесконечно много элементов, она (по мощности. — Перев.) будет все же не больше, чем множество всех положительных чисел. С каждым положительным целым числом n оказывается связанным определенное множество чисел Аn, имеющее имя на нашем языке — это позволяет представить себе, что все именуемые множества расположены в виде последовательности A₁, A₂…, А_n… (Если хотите, можете вообразить себе, например, книгу с бесконечным числом страниц, причем для каждого целого положительного n на соответствующей n-й странице приведено описание того или иного множества положительных целых чисел. Тогда система A_n — это множество, описанное на n-й странице этой книги.)

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

Далее, каждое утверждение x ? A_y имеет свой кодовый номер — число, которое, будучи записано в обычной десятичной системе счисления, состоит из цепочки единиц длиной x и следующей за ней цепочки нулей длиной у. Например, кодовый номер утверждения З ? A₂ выглядит как 11100; кодовый номер утверждения 1 ? A₅ имеет вид 100000. При этом кодовый номер утверждения x ? A_y, то есть число, состоящее из x единиц и следующих за ними у нулей, я буду обозначать символом x*y.

— Машина работает следующим образом, — продолжал Фергюссон. — Когда она обнаруживает, что число x принадлежит множеству A_y, то она отпечатывает число x*y, то есть кодовый номер утверждения x ? A_y. Если при этом машина печатает число x*y, то я говорю, что машина доказала утверждение x ? A_y. Кроме того, если машина способна напечатать число x*y, то я говорю, что утверждение x ? A_y доказуемо (с помощью моей машины).

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

— Минуточку, — вмешался Крейг. — Что значит «является истинным»? Какая разница между «является истинным» и «доказуемо»?

— Да это же совершенно разные вещи, — объяснил Фергюссон. — Я говорю, что утверждение x ? A_y истинно, если x действительно является элементом множества A_y. Если же оказывается, что машина способна напечатать число x*y, тогда я говорю, что утверждение x ? A_y доказуемо с помощью моей машины.

— Вот теперь ясно, — сказал Крейг. — Другими словами, утверждая, что ваша машина точна — или, иначе, что каждое утверждение, доказуемое с помощью машины, является истинным, — вы имеете в виду, что ваша машина никогда не напечатает число x*y, если x в действительности не принадлежит множеству A_y. Правильно я понял?

— Совершенно верно! — ответил Фергюссон.

— Скажите, а почему вы так уверены, что машина всегда точна? — спросил Крейг.

— Чтобы ответить на этот вопрос, я должен рассказать о ней более подробно, — ответил Фергюссон. — Дело в том, что машина работает на основе определенных аксиом относительно положительных целых чисел; эти аксиомы запрограммированы в машине в виде неких команд. Все эти аксиомы представляют собой хорошо известные математические истины. При этом машина не может доказать какое-либо утверждение, если оно не вытекает логически из этих аксиом. Но поскольку все аксиомы истинны, а любое логическое следствие из истинных утверждений тоже является истинным, то, стало быть, машина не способна доказать ложное утверждение. Если хотите, я могу перечислить эти аксиомы, и вы убедитесь сами, что машина действительно может доказывать только истинные утверждения.

— Сначала я хотел бы выяснить вот что, — сказал Мак-Каллох. — Допустим на некоторое время, что любое утверждение, доказуемое с помощью вашей машины, на самом деле является истинным. Значит ли это, что любое истинное утверждение вида x ? A_y доказуемо с ее помощью? Иначе говоря, способна ли ваша машина доказывать все истинные утверждения типа x ? A_y или только некоторые из них?

— Это очень важный вопрос, — ответил Фергюссон, — но, увы, ответа на него я не знаю. В этом-то как раз и состоит главная проблема, которую я никак не могу разрешить! Уже не один месяц я пытаюсь найти ответ на этот вопрос, но пока безуспешно. Так, я совершенно точно знаю, что моя машина может доказать любое утверждение вида x ? A_y, которое является логическим следствием заложенных в нее аксиом, однако я не знаю, достаточное ли количество аксиом введено мною в машину. Аксиомы, о которых идет речь, представляют собой нечто вроде общей суммы сведений, известных математикам относительно системы положительных целых чисел; и все же, может быть, их недостаточно, чтобы строго установить, какие же числа x и к каким поддающимся описанию множествам A_y принадлежат. До сих пор любое утверждение вида x ? A_y, которое я считал истинным, исходя из чисто математических соображений, оказывалось логическим следствием заложенных в машину аксиом; при этом машина способна доказать любое взятое мною утверждение такого вида. Однако то, что я не сумел найти истинного утверждения, которое машина не могла бы доказать, вовсе не означает, что такого утверждения не существует — может быть, я его просто еще не обнаружил. В то же время вполне может оказаться, что машина действительно способна доказать все истинные утверждения — но этого я тоже еще не сумел доказать. Пока я просто не знаю, как это сделать!

Короче говоря, после этого Фергюссон подробно объяснил Крейгу и Мак-Каллоху, какие аксиомы заложены в машину и какие чисто логические правила позволяют доказывать новые утверждения на основании уже имеющихся. Все эти подробности вполне убедили Крейга и Мак-Каллоха в том, что машина на самом деле точна — что она действительно доказывает лишь истинные утверждения. Однако вопрос о том, может ли машина доказать все истинные утверждения или только некоторые из них, так и остался нерешенным. На протяжении нескольких последующих месяцев они часто собирались вместе для детального обсуждения возникших вопросов — пока, наконец, задача не была полностью решена.

Я не стану утомлять читателя и приводить все подробности полученного ими решения; упомяну лишь о том, что действительно представляется для нас важным. Переломный момент в их исследованиях наступил тогда, когда друзья в конце концов сумели сформулировать три ключевые особенности машины; этого оказалось достаточно для полного решения задачи. Кажется, первыми обратили внимание на эти особенности Крейг и Мак-Каллох, однако их окончательная формулировка принадлежит Фергюссону. Но прежде чем перейти к описанию особенностей машины. я позволю себе сделать небольшое отступление.

Для любого множества А положительных целых чисел, под его дополнением A? понимается множество положительных целых чисел, не входящих в А. Например, если А — множество четных чисел, то его дополнением A? будет множество нечетных чисел; если А — множество чисел, делящихся на 5, то A? — это множество чисел, которые на 5 не делятся.

Для любого множества А положительных целых чисел под A* мы будем подразумевать множество всех положительных целых чисел х, для которых х*х является элементом множества А. Поэтому для любого числа x выражение «число x принадлежит множеству А*» эквивалентно выражению «число x*x принадлежит множеству А».

А теперь перечислим три главные особенности данной машины, которые были обнаружены Крейгом и Мак-Каллохом.

Свойство 1. Множество A₈ — это множество всех чисел, которые машина может напечатать.

Свойство 2. Для любого положительного целого числа n множество A_3·n является дополнением множества A_n. (При этом под символом 3·n мы понимаем 3, умноженное на n.)

Свойство 3. Для любого положительного целого числа n множество A_3·n+1 представляет собой множество A_n* (то есть множество всех чисел х, для которых число х*x принадлежит множеству A_n).

1. С помощью свойств 1–3 можно, оказывается, строго показать, что машина Фергюссона не способна доказать все истинные утверждения. Читателю предлагается найти такое утверждение, которое является истинным, но при этом не может быть доказано с помощью этой машины. Иначе говоря, мы должны найти такие числа n и m (они могут быть как одинаковыми, так и разными), для которых кодовый номер утверждения n ? A_m — то есть число n*m — не мог бы быть напечатан машиной, но чтобы при этом число n являлось бы элементом множества A_m.

2. В решении задачи 1, которое приведено ниже, числа n и m оба меньше 100. Имеется и другое решение этой задачи, для которого числа n, m также оказываются меньше 100 (при этом они опять могут быть как одинаковыми, так и разными). Сумеет ли читатель найти это решение?

3. Если не ограничивать сверху величину чисел n и m, то сколько всего решений может быть у такой задачи? Иначе, сколько существует истинных утверждений, которые недоказуемы с помощью машины Фергюссона?

Заключение

Фергюссон вовсе не хотел отказываться от идеи создания такой машины, которая могла бы доказывать арифметические истины, не будучи в состоянии доказывать ложные заключения, поэтому он напридумывал целую кучу таких логических машин.[7] Однако для каждой новой машины либо он сам, либо Крейг с Мак-Каллохом все-таки находили такое истинное утверждение, которое машина доказать не могла. Поэтому в конце концов Фергюссон отказался от мысли сконструировать чисто механическое устройство, которое было бы одновременно и точным (в указанном выше смысле. — Перев.), и могло бы доказать любое истинное арифметическое утверждение.

Итак, все героические попытки Фергюссона не увенчались успехом, однако причина этого заключалась отнюдь не в недостатке авторской изобретательности. Мы не должны забывать о том, что он жил за несколько десятилетий до знаменитых открытий таких известных логиков, как Гёдель, Тарский, Клини, Тьюринг, Пост, Черч и другие ученые, о работах которых у нас вот-вот пойдет речь. Если бы Фергюссон дожил до этих открытий, то он понял бы, что неудачи его обусловлены исключительно тем, что он пытался создать нечто по сути своей совершенно невозможное! Поэтому, отдав должное Фергюссону и его коллегам Крейгу и Мак-Каллоху, распрощаемся с ними и перенесемся на три-четыре десятилетия вперед, в переломный 1931 год.