Неполнота, неостановка, невычислимость

Lowrence Hall of Science оказался игровой площадкой. Т.е. там много интересного, конечно, но в основном для детей младших классов. А я не знал, пешком шлепал в немалую такую гору над Беркли. Помимо детского музея там есть и детский магазин. К счастью, для скучающих родителей в нем лежит несколько десятков взрослых книжек. Мое внимание привлекла Meta Math американского ученого из Аргентины  Gregory Chaitin'a. Книжка сама по себе довольно спорная, и автор неприкрыто любит себя, но тем не менее приоткрывает очень интересные проблемы, которые как бы сами по себе и известны многим, но все вместе и взаимосвязано подаются нечасто.

Meta Math -- это основние математики, теория доказательств и универсальная аксиоматика Дэвида Гильберта. Чайтин рассуждает о трех фундаментальных результатах: теореме Гёделя о неполноте, проблеме остановки Тьюринга и своем собственном результате -- числе "омега", вероятности остановки программы. Сюда же примыкает тема случайности  и сложности, но со стороны компрессии и информации, т.е. сложность определенной информации, набора битов,  -- как минимальная длина программы, необходимая для генерации этого набора.

Чайтин утверждает, что в этих проблемах заключено само Бытие или Бог, как кому нравится. Бог глядит на нас через невычисляемые числа, смеется над нашими попытками определить, остановится ли программа, и подсовывает недоказумемые в принципе положения. Он много цитирует Лейбница, который придумал двоичную алгебру и еще много веков назад предположил, что 1 -- это Бытие, 0 -- это ничто, и комбинация нулей и единиц пораждает Вселенную.

Пересказывать дальше не буду, но это одна из самых интересных книг по математики для НЕ-математиков, которые я когда-либо читал.

Update от 26-01: А вот тема для размышления.

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

P.S. Впрочем, не зря я все таки на гору залез.
( Вид на Беркли и Сан-Франциско )