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

[kaipa]

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

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

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

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

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

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

P.S. Впрочем, не зря я все таки на гору залез.

Comments

[vt-qveant.livejournal.com]

а правильно ли считать, что сейчас "метаматематика", "основания математики" и "математическая логика" суть одно и то же? (Если не указывать специально Гильберта).

> сложность <...> как минимальная длина программы, необходимая для генерации этого набора
колмогоровская

[ushastyi.livejournal.com]

Я бы сказал, что математическая логика -- это одно из оснований математики, которое входит в мета-матиматику :)

Вот оказалось, что этот товарищ свое имя рядом с Колмогоровым ставит, даже в википедии так:
http://en.wikipedia.org/wiki/Kolmogorov_complexity -- Kolmogorov-Chaitin complexity в качестве одного из названий.