Наука на просторах Интернета
Шимон Давиденко
От Гёделя до Азимова
"Млечный путь" продолжает публиковать наиболее интересные научно-популярные статьи, опубликованные на интернет-портале MEDIUM.
Что на самом деле говорит нам Гёдель о математике
Дэрил Купер
Существует миф, окружающий теорему Гёделя о неполноте: что математика каким-то образом ограничена или несовершенна: что существуют математические истины, которые нельзя доказать.
Это, в лучшем случае, полуправда и, как я объясню, довольно глупая. Она скрывает самый мощный математический инструмент, который нам дала логика.
На самом деле история такова: математики могут путешествовать в другие математические вселенные, где возможны вещи, которые невозможны в нашей, а затем приносить с собой знания в нашу вселенную. Гёдель показал нам, как это делать.
Числа - это не то, что вы думаете
Первый момент: мы точно не знаем, что такое числа, и никогда не узнаем. Проблема в том, чтобы знать, где заканчивается конечное и начинается бесконечное. Мы думаем, что знаем, что значит "конечный", но это иллюзия. Мы склонны представлять натуральные числа (счетные числа) 0, 1, 2, 3,... как простые объекты, природу которых мы постигаем непосредственно. Но проблема заключается именно в этих точках...
Никто никогда не объяснил вам точно, что они означают, потому что никто не может. Многие люди представляют себе числа как последовательности цифр: 12345, 6145987145 или, возможно, какую-то гораздо более длинную последовательность. Но сколько там цифр? Единственный возможный ответ - некоторое количество цифр, что ни к чему не приводит.
Другой распространенный образ - это цифры, расположенные вдоль бесконечной линии. Но и это замкнутый круг, без каламбура. Какова длина этой линии? Линия не объясняет целые числа; она предполагает их. Или, возможно, вы думаете о бесконечном подсчете. Проблема в том, что точная длина "вечности" скрывает проблему. Мы говорим о отрезке времени (бесконечном), который слишком велик, чтобы иметь какой-либо физический смысл.
Все эти мысленные образы основаны на физической реальности, но это категориальная ошибка. Числа - это абстракции. Они не являются физическими сущностями. Они не принадлежат к физическому миру, а принадлежат к Иному миру - миру идей, концепций, абстракций. Примером чего-либо из Иного мира является алгоритм, например, сортировка деревьями.
Существует множество практических реализаций, но сам алгоритм абстрактен, он принадлежит к Иному миру. В любом случае, физическая реальность причудлива, и мы понятия не имеем, что она собой представляет на самом деле, скажем, ниже планковской длины (наименьшего физически значимого расстояния), и та же проблема существует со временем.
Эта цикличность определения безвредна для практических целей, даже в физике и технике. В этих областях 100 десятичных знаков считаются огромной цифрой. Для большинства практических целей число - это то, что можно написать в одну строку или ввести в калькулятор. Самые точные физические измерения едва превышают 14 десятичных знаков, хотя математики вычислили более 60 триллионов знаков числа пи.
Математика заставляет нас сталкиваться с числами, которые не просто велики, а настолько велики, что концептуальная граница между конечным и бесконечным становится психологически бессмысленной. Например, сколько разных коротких романов возможно написать на английском языке, скажем, каждый не более 60 000 слов?
Ответ: больше 1, за которым следует миллион нулей. Это довольно много. Такое количество книг многократно заполнило бы наблюдаемую Вселенную - и всё же по математическим меркам это совершенно незначительно. Количество способов расположить эти книги по порядку на полке больше 1, за которым следует множество нулей. Под "множеством" я подразумеваю больше 1, за которым следует миллион нулей. И так далее.
Это даже не начинает описывать, насколько большими могут быть числа. Теперь перейдём к ещё большим числам. Существуют так называемые последовательности Гудштейна. Вы начинаете с числа, например, 4, и многократно повторяете одну и ту же операцию: переписываете число в наследственной системе счисления, увеличиваете основание на единицу, затем вычитаете 1. Долгое время это приводит к взрывному росту чисел, прежде чем они в конечном итоге схлопываются к нулю. Если вы начинаете с 4, количество шагов, необходимых для достижения нуля, превышает 1, за которым следуют 100 миллионов нулей. Википедия описывает это число, начиная с 5, и удачи вам, если вы сможете понять ответ.
Если вы начинаете с немного большего числа, например, 19, нет разумного способа понять, сколько шагов требуется. Число просто слишком велико. И все же оно конечно. Это поднимает глубокий вопрос: если число настолько велико, как интуиция отличает его от бесконечности?
Существует множество других примеров таких больших чисел - число Грэма, числа гидры и многие другие. Однако величина - это лишь часть проблемы. Другая трудность - вычислимость. Существуют конечные определяемые числа, для которых невозможно, даже в принципе, вычислить. Эти числа не являются расплывчатыми, мистическими или спекулятивными. Они точно определены, естественным образом возникают в логике и вычислениях, и тем не менее полностью опровергают любые попытки понять их величину. Их невозможно записать. Никогда. Но они существуют. Логика говорит...
Итак. Некоторые целые числа существуют не потому, что мы можем их построить, а потому, что логика заставляет их существовать. Их определения не позволяют нам их вычислить; они объясняют только, почему они должны существовать. Наглядная иллюстрация этого явления - из теоретической информатики. Посмотрите на все компьютерные программы длиной 1919, которые в конечном итоге останавливаются. Некоторые останавливаются быстро; другим требуется больше времени. Одна из них останавливается последней. Количество шагов, которые она делает, конечно, но его буквально невозможно вычислить. Оно намного больше, чем практически любое число, которое вы можете себе представить.
Погуглите Busy Beaver, если хотите узнать больше.
Гёдель
Многие знают, что Гёдель показал, что существуют "истинные" математические утверждения, которые нельзя доказать. Этот результат называется теоремой Гёделя о неполноте. Как это захватывающе! Существует бесчисленное множество книг и видеороликов об этом. Некоторые философы и физики в восторге от этого. Они говорят, что человеческий разум может постичь истины, недоступные компьютерам. Что гораздо менее известно, так это то, что Гёдель первым доказал теорему Гёделя о полноте. Упрощенное изложение здесь противоположно: каждое истинное математическое утверждение можно доказать. Как скучно!
Но как же оба результата могут быть верны? Ответ