|
Итак, все героические попытки Фергюссона не увенчались успехом, однако причина этого заключалась отнюдь не в недостатке авторской изобретательности. Мы не должны забывать о том, что он жил за несколько десятилетий до знаменитых открытий таких известных логиков, как Гёдель, Тарский, Клини, Тьюринг, Пост, Черч и другие ученые, о работах которых у нас вот-вот пойдет речь. Если бы Фергюссон дожил до этих открытий, то он понял бы, что неудачи его обусловлены исключительно тем, что он пытался создать нечто по сути своей совершенно невозможное! Поэтому, отдав должное Фергюссону и его коллегам * Некоторые из них оказались весьма интересными, и о них я надеюсь рассказать в своей следующей книге. Стр. 172 Крейгу и Мак-Каллоху, распрощаемся с ними и перенесемся на три-четыре десятилетия вперед, в переломный 1931 год. Решени 1. Одно из решений состоит в следующем: утверждение 75ЄА75 является истинным, но не может быть доказано машиной. И вот почему. Допустим, что утверждение 75ЄА75 ложно. Тогда число 75 не принадлежит множеству А75- Следовательно, это число должно принадлежать множеству А25 (согласно свойству 2, множество Аn является дополнением множества ais)- Это означает (согласно свойству 3), что число 75*75 принадлежит множеству А8, поскольку 25=3X8-1-1, и, следовательно, машина может напечатать число 75*75. Иначе говоря, это означает, что утверждение 75еЛ?5 может быть доказано машиной. Таким образом, если бы утверждение 75ЄA?5 было ложным, то оно вполне могло бы быть доказано машиной. Однако нам известно по условию, что машина точна и никогда не доказывает ложные утверждения. Поэтому утверждение 75ЄA75 не может оказаться ложным, и, стало быть, оно должно быть истинным. Далее, поскольку утверждение 75ЄА75 истинно, то число 75 действительно принадлежит множеству Аn. Поэтому оно не может принадлежать множеству А 25 (согласно свойству 2), и, следовательно, число 75 * 75 в свою очередь не может принадлежать множеству А8, поскольку если бы это было так, то тогда, согласно свойству 3, число 75 принадлежало бы множеству а25. Поскольку ясно, что число 75 * 75 не принадлежит множеству Ag, то утверждение 756А75 не может быть доказано машиной. Итак, утверждение 75ЄA75 является истинным, но оно недоказуемо с помощью машины. 2. Прежде чем рассматривать другие решения, установим следующий факт весьма общего свойства. Пусть для всего дальнейшего ключевым является множество К—это множество всех чисел х, для которых утверждение хЄАx недоказуемо машиной, или, что то же самое, множество таких чисел х, для которых число — 106 —
|