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

Самое главное, что ? дает нам бесконечное число неприводимых битов. Любая программа конечной длины, сколько миллиардов битов она бы ни содержала, не поможет нам определить оставшиеся биты, которых бесконечно много. Иными словами, при любом конечном наборе аксиом мы имеем бесконечное число истин, которые не могут быть доказаны с помощью этого набора.

Почему число ? несжимаемо?

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

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

Посмотрим теперь, как знание N битов ? позволит решить задачу останова и определить, какие из всех программ длиной до N битов будут останавливаться. Сделаем это поэтапно. На K-м этапе будем прогонять каждую программу в течение K секунд и по числу остановившихся программ определять вероятность остановки ?K. Она окажется меньше ?, поскольку будет получена с использованием лишь подмножества программ, которые в конце концов останавливаются, тогда как ? рассчитывается с использованием всех программ. С увеличением K значение ?K будет приближаться к ?, и все больше первых битов ?K будут становиться равными соответствующим битам ?. Когда первые N битов ?K и ? совпадут, это будет значить, что учтены все программы длиной до N битов, которые рано или поздно останавливаются. (Если бы существовала еще какая-то программа длиной N битов, она остановилась бы на более позднем этапе K, и тогда ?K оказалось бы больше ?, что невозможно.)

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

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

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

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

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

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

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