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

Современная математическая теория алгоритмической информации позволила дать точные количественные определения понятиям сложности и простоты. Обычная теория информации определяет объем информации числом битов, необходимых для ее кодирования. Например, для кодирования простого ответа ?да/нет? нужен один бит. В отличие от этого, объем алгоритмической информации определяется длиной компьютерной программы, необходимой для генерации данных. Минимальное число битов, необходимых для хранения программы, называется количеством алгоритмической информации данных. Например, бесконечный ряд натуральных чисел 1, 2, 3,... содержит очень мало алгоритмической информации: все числа ряда можно получить с помощью коротенькой компьютерной программы. Не имеет значения, сколько времени понадобится для выполнения вычислений и какой объем памяти придется использовать, важна лишь длина программы в битах. (Разумеется, точное значение количества алгоритмической информации зависит от выбранного языка программирования, однако для рассматриваемых в данной статье вопросов это несущественно.)

В качестве другого примера возьмем число ?, равное 3,14159... Количество алгоритмической информации в нем тоже невелико: для последовательного вычисления всех его знаков нужен довольно короткий алгоритм. А вот случайное число, содержащее всего миллион знаков, скажем, 1,341285...64, характеризуется гораздо б?льшим количеством алгоритмической информации. Поскольку в таком числе нет определяющей структуры, длина самой короткой программы, необходимой для его написания, будет близка к длине самого числа:

Начать

Напечатать ?1,341285...64?

Конец

Научная теория подобна компьютерной программе, предсказывающей результаты наблюдений. Полезная теория представляет собой сублимацию экспериментальных данных: с помощью нескольких законов и уравнений можно описать целый мир различных явлений (изображение: www.sciam.ru)

(В программу должны быть включены все цифры, замененные многоточием.) Никакая более короткая программа не позволит рассчитать подобную последовательность цифр: ее невозможно сжать, в ней нет избыточности. Самое лучшее, что можно сделать, ? просто передать ее, как она есть. Такие последовательности называются неприводимыми или алгоритмически случайными.

Как же соотносятся вышесказанное с научными законами и фактами? Идея заключается в том, чтобы взглянуть на науку глазами программиста: научная теория подобна компьютерной программе, предсказывающей результаты наблюдений, т.е. экспериментальные данные. Такая точка зрения опирается на два фундаментальных принципа. Согласно первому (?бритва Оккама?), из двух теорий, объясняющих некоторые данные, следует предпочесть более простую. Иначе говоря, наилучшей теорией является самая короткая программа, позволяющая рассчитать результаты наблюдений. Второй принцип, изложенный Лейбницем, в современных понятиях звучит так: теория, объем которой в битах равен количеству объясняемых ею данных, бесполезна, поскольку теорией такого размера можно описать совершенно случайные данные. Полезная теория обеспечивает сокращение количества информации: осмысление данных ? это их сжатие в краткие алгоритмические описания. Чем проще теория, тем лучше понимание сути явления.

Достаточная причина

Лейбниц, живший за два с половиной века до появления компьютерных программ, очень близко подошел к современному понятию алгоритмической информации. Лейбниц знал, что все можно представить в виде двоичных кодов, и создал одно из первых вычислительных устройств; рассматривая понятия сложности и простоты, он осознавал огромный потенциал вычислений. Если бы Лейбниц объединил все известные ему элементы, то, скорее всего, усомнился бы в одном из устоев своей философии ? принципе достаточной причины, согласно которому все происходящее имеет причину. Более того, если какое-то положение истинно, то оно истинно по какой-то причине. Бывает, что в суете и хаосе повседневной жизни в это трудно поверить. Даже если мы не всегда можем увидеть причину (возможно потому, что цепочка рассуждений слишком длинна и запутанна), ее видит Бог. Вот и всё! Здесь Лейбниц соглашался с древнегреческими авторами этой идеи.

Математики, несомненно, безоговорочно принимают принцип достаточной причины Лейбница, потому что всегда стремятся всё доказать. Даже если истинность теоремы очевидна, и миллионы примеров подтверждают ее, математики все равно требуют обобщенного доказательства, на меньшее они не согласны. И здесь концепция алгоритмической информации может внести удивительный вклад в философские рассуждения об источниках и пределах познания. Она показывает, что некоторые математические факты истинны безо всяких причин, и бросает вызов принципу достаточной причины. Как будет показано ниже, существует бесконечное число неприводимых математических фактов, истинность которых нельзя объяснить никакой теорией. Они неприводимы не только вычислительно, но и логически. ?Доказать? эти факты можно только одним способом: признать их аксиомами без всяких рассуждений.

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

В древней Греции, чтобы убедить сограждан проголосовать именно так, а не иначе, вы должны были бы привести им свои доводы. Вероятно, именно поэтому греки пришли к мысли, что математические положения нужно доказывать, а не выводить опытным путем. (В отличие от греков, древнейшие цивилизации Месопотамии и Египта, похоже, полагались на эксперимент.) Метод логических рассуждений оказался чрезвычайно плодотворным: с его помощью были созданы современная математика, математическая физика и все точные науки, включая технологию создания компьютеров ? в высшей степени математичных и логичных машин. Утверждаю ли я, что подход, на котором математика и вся наука строились в течение двух тысячелетий, терпит крах? В каком-то смысле да. Моим контрпримером, иллюстрирующим ограниченность возможностей логики и рассуждений, моим источником бесконечного потока недоказуемых математических положений является число, которое я назвал ?омега? (?).

Число ?

Первый шаг к открытию числа ? был сделан в знаменитой статье, опубликованной ровно через 250 лет после издания эссе Лейбница. В 1936 году на страницах ?Трудов Лондонского математического общества? (Proceedings of the London Mathematical Society) Алан Тьюринг впервые представил математическую модель простой универсальной вычислительной машины. Кроме того, он задался вопросом: можно ли определить, остановится когда-нибудь компьютерная программа или нет? Так была сформулирована знаменитая проблема останова.