Короче говоря, после этого Фергюссон подробно объяснил Крейгу и Мак-Каллоху, какие аксиомы заложены в машину и какие чисто логические правила позволяют доказывать новые утверждения на основании уже имеющихся. Все эти подробности вполне убедили Крейга и Мак-Каллоха в том, что машина на самом деле точна — что она действительно доказывает лишь истинные утверждения. Однако вопрос о том, может ли машина доказать все истинные утверждения или только некоторые из них, так и остался нерешенным. На протяжении нескольких последующих месяцев они часто собирались вместе для детального обсуждения возникших вопросов — пока, наконец, задача не была полностью решена.
Я не стану утомлять читателя и приводить все подробности полученного ими решения; упомяну лишь о том, что действительно представляется для нас важным. Переломный момент в их исследованиях наступил тогда, когда друзья в конце концов сумели сформулировать три ключевые особенности машины; этого оказалось достаточно для полного решения задачи. Кажется, первыми обратили внимание на эти особенности Крейг и Мак-Каллох, однако их окончательная формулировка принадлежит Фергюссону. Но прежде чем перейти к описанию особенностей машины. я позволю себе сделать небольшое отступление.
Для любого множества А положительных целых чисел, под его дополнением A̅ понимается множество положительных целых чисел, не входящих в А. Например, если А — множество четных чисел, то его дополнением A̅ будет множество нечетных чисел; если А — множество чисел, делящихся на 5, то A̅ — это множество чисел, которые на 5 не делятся.
Для любого множества А положительных целых чисел под A* мы будем подразумевать множество всех положительных целых чисел х, для которых х*х является элементом множества А. Поэтому для любого числа x выражение «число x принадлежит множеству А*» эквивалентно выражению «число x*x принадлежит множеству А».
А теперь перечислим три главные особенности данной машины, которые были обнаружены Крейгом и Мак-Каллохом.
Свойство 1. Множество A>8 — это множество всех чисел, которые машина может напечатать.
Свойство 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 можно, оказывается, строго показать, что машина Фергюссона не способна доказать все истинные утверждения. Читателю предлагается найти такое утверждение, которое является истинным, но при этом не может быть доказано с помощью этой машины. Иначе говоря, мы должны найти такие числа