|
Стр. 170 прежде чем перейти к описанию особенностей машины. я позволю себе сделать небольшое отступление. Для любого множества А положительных целых чисел, под его дополнением А понимается множество положительных целых чисел, не входящих в А. Например, если А—множество четных чисел, то его дополнением А будет множество нечетных чисел; если А— множество чисел, делящихся на 5, то А—это множество чисел, которые на 5 не делятся. Для любого множества А положительных целых чисел под А* мы будем подразумевать множество всех положительных целых чисел х, для которых х*х является элементом множества А. Поэтому для любого числа х выражение «число х принадлежит множеству А*» эквивалентно выражению «число х*х принадлежит множеству А». А теперь перечислим три главные особенности данной машины, которые были обнаружены Крейгом и Мак-Каллохом. Свойство 1. Множество А8 — это множество всех чисел, которые машина может напечатать. Свойство 2. Для любого положительного целого числа n множество Л3„ является дополнением множества А3n. (При этом под символом 3-n мы понимаем 3, умноженное на и.) Свойство 3. Для любого положительного целого числа и множество A3.n+1 представляет собой множество An* (то есть множество всех чисел х, для которых число х*x принадлежит множеству An). 1. С помощью свойств 1—3 можно, оказывается, строго показать, что машина Фергюссона не способна доказать все истинные утверждения. Читателю предлагается найти такое утверждение, которое является истинным, но при этом не может быть доказано с помощью этой машины. Иначе говоря, мы должны найти такие числа пит (они могут быть как одинаковыми, так и разными), для которых кодовый номер утверждения nЄАn—то есть число n*m —не мог бы быть напечатан машиной, но чтобы при этом число n являлось бы элементом множества А п. Стр.171 2. В решении задачи 1, которое приведено ниже, числа пит оба меньше 100. Имеется и другое решение этой задачи, для которого числа n, m также оказываются меньше 100 (при этом они опять могут быть как одинаковыми, так и разными). Сумеет ли читатель найти это решение? 3. Если не ограничивать сверху величину чисел n m, то сколько всего решений может быть у такой задачи? Иначе, сколько существует истинных утверждений, которые недоказуемы с помощью машины Фергюссона?[ Заключение Фергюссон вовсе не хотел отказываться от идеи создания такой машины, которая могла бы доказывать арифметические истины, не будучи в состоянии доказывать ложные заключения, поэтому он напридумывал целую кучу таких логических машин*. Однако для каждой новой машины либо он сам, либо Крейг с Мак-Каллохом все-таки находили такое истинное утверждение, которое машина доказать не могла. Поэтому в конце концов Фергюссон отказался от мысли сконструировать чисто механическое устройство, которое было бы одновременно и точным (в указанном выше смысле.— Перев.), и могло бы доказать любое истинное арифметическое утверждение. — 105 —
|