Коллектив авторов - Теорема Геделя о неполноте [Фейк]

Итак, зная первые N битов ?, можно решить задачу останова для всех программ длиной до N битов. Предположим теперь, что первые N битов ? можно определить с помощью программы длиной существенно меньше N битов. Тогда ее можно объединить с программой вычисления ?K и получить в итоге программу длиной меньше N битов для решения проблемы останова для всех программ длиной до N битов. Однако, как сказано выше, такой программы существовать не может. Следовательно, для вычисления первых N битов ? требуется программа длиной почти N битов. Этого достаточно, чтобы признать число ? несжимаемым, т.е. неприводимым. (Для больших N сокращение длины с N битов до почти N битов несущественно.)

Из неприводимости числа ? следует, что всеобъемлющей математической теории существовать не может. Бесконечное множество битов ? составляет бесконечное множество математических фактов (является ли каждый выбранный бит единицей или нулем), которые не могут быть выведены из каких бы то ни было принципов, более простых, чем сама последовательность битов. Значит, сложность математики бесконечна, тогда как любая отдельная теория ?всего на свете? характеризуется конечной сложностью и, следовательно, не может охватить все богатство мира математических истин. Из сказанного отнюдь не следует, что от доказательств нет никакого толка, и я ни в коем случае не против логических рассуждений. На самом деле, неприводимые принципы (аксиомы) всегда составляли часть математики. Просто число ? показывает, что их гораздо больше, чем предполагалось ранее.

Обзор: неприводимая сложность

* Курт Гедель показал неизбежную неполноту математики: в ней существуют истинные положения, которые невозможно строго доказать. Особое число ? выявляет еще б?льшую неполноту и свидетельствует о существовании бесконечного множества теорем, которые нельзя вывести из конечного набора аксиом.

* Число ? строго определено и имеет вполне конкретное значение, но вычислить его с помощью конечной компьютерной программы невозможно.

* Анализ свойств числа ? показывает, что математикам иногда следует постулировать новые аксиомы. Именно так поступают физики, которые обобщают результаты экспериментов и выводят фундаментальные законы, недоказуемые с помощью логики.

Возможно, математикам не нужно пытаться все доказать. Иногда им следует просто добавлять новые аксиомы, когда дело доходит до неприводимых фактов. Проблема в том, чтобы понять, что они неприводимы, и признать, что их невозможно доказать. Однако математики никогда не сдадутся, в отличие от физиков, которые всегда готовы обойтись правдоподобными рассуждениями вместо строгих доказательств, и охотно выводят новые законы, чтобы осмыслить свежие экспериментальные данные. Возникает интересный вопрос: похожа ли математика на физику?

Математика и физика

Принято считать, что математика и физика совершенно не похожи друг на друга. Физики описывают мир, исходя из результатов экспериментов и наблюдений. Законы, управляющие Вселенной, будь то законы Ньютона или Стандартная модель физики элементарных частиц, должны устанавливаться эмпирически и затем приниматься за аксиомы, которые невозможно доказать логическим путем, а можно лишь проверить экспериментально. Математики же в некотором смысле независимы от мира. Их выводы и теоремы, например, свойства целых или вещественных чисел, никак не зависят от окружающей нас реальности. Математические истины должны быть верны в любом мире. И все же определенное сходство есть. В физике, и вообще в естественных науках, ученые формулируют законы, сублимируя результаты наблюдений. Затем они показывают, как результаты наблюдений могут быть выведены из получившихся законов. В математике происходит нечто подобное: математики сжимают результаты вычислительных экспериментов в аксиомы, а затем выводят из них теоремы.

Если бы Гильберт оказался прав, то математика была бы замкнутой системой, в которой нет места новым идеям. Существовала бы статичная замкнутая теория, объясняющая в математике все, и это было бы похоже на диктатуру. Чтобы математика развивалась, нужны новые идеи и простор для творчества. Недостаточно усердно работать, выводя все возможные следствия из фиксированного числа базовых принципов. Лично мне больше нравятся открытые системы, я не люблю жестких, авторитарных способов мышления.

Имре Лакатош (Imre Lakatos), бежавший в 1956 году из Венгрии и впоследствии занимавшийся философией науки в Англии, тоже считал, что математика похожа на физику. Он ввел понятие квазиэмпиричности, чтобы показать, что и математике не чужды эксперименты. Например, еще в 1742 году Кристиан Гольдбах опытным путем пришел к предположению, что любое четное число больше двух можно представить в виде суммы двух простых чисел. Предположение Гольдбаха успешно проверено для чисел до 1014, но строго не доказано. Мне кажется, что математика квазиэмпирична. Иными словами, она отличается от физики (которая истинно эмпирична), но, вероятно, не так сильно, как полагает большинство людей.

Новые аксиомы

Идея добавления новых аксиом не чужда математикам. Возьмем для примера пятый постулат Евклида: через выбранную точку, лежащую вне прямой, можно провести только одну прямую, параллельную данной. Столетиями геометры ломали голову, пытаясь доказать это, исходя из остальных постулатов Евклида. Не удалось. Наконец, математики поняли, что пятую аксиому можно заменить и получить неевклидову геометрию криволинейных пространств, в частности сферического и седлообразного. Другим примером может служить закон исключенного среднего в логике и аксиома выбора в теории множеств, которыми охотно пользуется в своих доказательствах большинство математиков. Но ведь есть ученые, которые их не признают и исследуют так называемую интуиционистскую логику и конструктивистскую математику. Оказывается, математика пока не стала монолитной системой абсолютных истин!

Другой очень интересной аксиомой может стать утверждение ?P не равно NP?, где P и NP ? названия классов задач. К классу NP относятся задачи, для которых предлагаемое решение можно проверить очень быстро. Например, для задачи ?найти множители числа 8 633? предлагаемое решение ?97 и 89? быстро проверяется простым перемножением. (Существует строгое определение понятия ?быстро?, но подробности здесь не имеют значения.) Класс P составляют задачи, которые можно быстро решить, не имея предварительного предположения. Вопрос, ответа на который не знает никто, состоит в том, можно ли быстро решить любую задачу класса NP. (Есть ли способ быстро найти множители числа 8 633?) Иначе говоря, тождественны ли классы P и NP? Это один из пунктов списка ?Проблем тысячелетия? Математического института Клэя (Clay Millennium Prize Problem), за решение каждой из которых назначена награда в $1 млн.