Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики

Статья называлась «Система логики, основанная на порядковых числах», и некоторые читатели будут уже знакомы со способом записи Канторовых порядковых чисел , который я применял для субиндексов. Иерархия логических систем, которые получаются с помощью приведенной мной процедуры, описывается с помощью вычислимых порядковых чисел .

Есть несколько довольно естественных и легко формулируемых математических теорем, которые, если их пытаться доказать путем использования стандартных (введенных Пеано) правил арифметики, привели бы к «гипертрофированной» геделевской процедуре (по числу шагов многократно превосходящей ту, что я описал ранее). Математические доказательства этих теорем по природе своей не зависят от туманных и сомнительных рассуждений, выходящих за рамки аппарата нормального математического доказательства (см. Сморински [1983]).

Делается различие между «множествами» и «Классами», где «множества» могут быть собраны вместе для образования других множеств или классов; а классы не могут образовывать сколько-нибудь более крупные объединения, будучи для этого «слишком большими». Однако не существует правила, согласно которому можно было бы решать, какие объединения могут рассматриваться как множества, а какие с необходимостью должны быть только классами — если не считать «порочно» замкнутое правило, гласящее, что множествами являются те объединения, которые можно составлять вместе, чтобы получать новые объединения!

Континуум-гипотеза, которая упоминалась в главе 3, (конец подглавы «Сколько же всего действительных чисел?», и из которой следует, что С= N 1), является наиболее «экстремальным» математическим утверждением, которое здесь встречается (хотя часто рассматриваются и куда более «экстремальные» рассуждения). Континуум-гипотеза интересна еще и потому, что сам Гедель, совместно с Полом Дж. Коэном, показал, что эта гипотеза в действительности не зависит от стандартных аксиом и правил теории множеств. Таким образом, отношение любого математика к континуум-гипотезе позволяет причислить его к сторонникам либо формалистской, либо платонистской точки зрения. Для формалиста данная гипотеза будет «недоказуемой», поскольку ее справедливость не может быть установлена или опровергнута, если опираться на стандартную (построенную Цермело и Френкелем) формальную систему, и, значит, не «имеет смысла» называть ее ни «истинной», ни «ложной». Однако, для убежденного платониста эта гипотеза является либо истинной, либо ложной, хотя какой именно — это можно установить только путем рассуждений некоторого нового типа, идущих еще дальше, чем использование геделевских утверждений для формальной системы Цермело — Френкеля. (Коэн [1966] сам предложил принцип рефлексии, который позволяет показать, что континуум-гипотеза — «с очевидностью ложна»!)

Живое и не слишком насыщенное техническими деталями изложение этой темы можно найти у Ракера [1984].

Интуиционизм был назван так потому, что ему предназначалось служить отражением человеческой мысли.

Сам Брауэр начал размышлять в этом направлении, в частности, потому, что очень придирчиво и болезненно относился к «неконструктивности» доказательства своей теоремы из области топологии, «теоремы Брауэра о неподвижной точке». Эта теорема утверждает, что, если вы возьмете круг — то есть окружность вместе со всеми точками внутри нее — и будете непрерывно двигать его внутри области, где он находился изначально, то найдется по крайней мере одна точка круга, — называемая неподвижной точкой, — которая окажется точно там же, откуда она начала движение. Не ясно, где именно располагается эта точка, и может ли их быть несколько — теорема говорит только о существовании такой точки. (Среди математических теорем существования, эта, на самом деле, носит довольно «конструктивный» характер. Примеры теорем существования более высокой степени неконструктивности ― это теоремы, зависящие от так называемой «аксиомы выбора» или «леммы Цорна» (см. Коэн [1966], Ракер [1984]).) Трудность в случае Брауэра была аналогична той, что возникает в следующей задаче: найти точки, в которых f обращается в нуль, если известно, что f — действительная непрерывная функция действительной переменной, которая принимает как положительные, так и отрицательные значения. Стандартная процедура заключается в последовательном делении пополам отрезка, на котором функция меняет свой знак; но решение о том, какое именно промежуточное значение принимает функция (положительное, отрицательное или нулевое), может оказаться неконструктивным в том смысле, которого требует Брауэр.

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

''Доказательство могло бы, в действительности, состоять из последовательности шагов, которые отражали бы действие машины, продолжающееся до ее остановки. Доказательство завершалось бы, как только машина остановится.

Мы нумеруем множества { v , ω , x …., z ], где v представляет функцию f в согласии с некоторой лексикографической схемой. Мы (рекурсивно) проверяем на каждом этапе справедливость равенства f ( ω , x …, z ) = 0 и оставляем утверждение E к.с. ω , х …., z [( ω , х …., z ) = 0 ] только в том случае, если это равенство выполняется.

Последняя теорема Ферма доказана английским математиком Эндрю Уайлсом (Andrew J. Wiles). Доказательство опубликовано в 1995 году. — Прим. ред .

Недавно я узнал от Леоноры Блюм, что (заинтересовавшись моими комментариями в первом издании этой книги) она установила, что множество Мандельброта (и его дополнение) на самом деле являются, как я и предполагал, нерекурсивными в том смысле, который описан в десятом примечании.

Блюмом, Шубом и Смэйлом [1989] была разработана новая теория вычислимости для действительных функций от действительных переменных (в отличие от общепринятых функций натуральных чисел, принимающих натуральные значения), подробности которой я узнал лишь совсем недавно. Эта теория применима и к комплексным функциям, а кроме того, может сыграть заметную роль в упомянутых мной вопросах.