Принцесса или тигр

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

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

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

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

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

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

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

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

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

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

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