Карта → событие
Чейтин: число, которое нельзя вычислить
Определение случайности есть, проверить его алгоритмом нельзя. Чейтин выяснил, насколько плохо дело: не только алгоритм не справится — не справится и математика.
Потолок сложности
Теорема Чейтина о неполноте (1974). Для всякой формальной системы существует такая постоянная $c$, что система не может доказать ни одного утверждения вида
$$K(x) > c$$
— ни для какого конкретного слова $x$. При этом слов со сложностью больше $c$ — подавляющее большинство.
Постоянная $c$ примерно равна длине записи самой системы: её аксиом и правил вывода. Иначе говоря, у каждой теории есть свой потолок сложности, и он равен её собственному размеру. Про объекты сложнее себя теория ничего доказать не может.
Доказательство: тот же парадокс Берри, только формально
Пусть система $S$ непротиворечива и доказывает утверждения вида $K(x) > L$ для сколь угодно больших $L$.
Напишем программу $P$: в неё зашито число $L$; она перебирает все выводы системы $S$ подряд и печатает первое слово $x$, для которого нашёлся вывод утверждения $K(x) > L$.
Длина $P$ — это фиксированный кусок (перебор выводов, запись самой системы) плюс запись числа $L$, то есть $|P| \leqslant c_0 + \log_2 L$.
Но $P$ печатает $x$, значит $K(x) \leqslant |P| \leqslant c_0 + \log_2 L$. А система доказала, что $K(x) > L$, и если она не лжёт, то
$$L \;<\; K(x) \;\leqslant\; c_0 + \log_2 L .$$
При достаточно большом $L$ это неверно: логарифм растёт медленнее аргумента. Противоречие. Значит, система доказывает утверждения $K(x) > L$ только для $L$, не превосходящих некоторого $c$.
Что это добавляет к Гёделю
Гёдель предъявил недоказуемое утверждение, построенное самоссылкой, — и оно выглядело нарочно сделанным, кунштюком. Чейтин показывает другое: недоказуемых утверждений не просто много, они типичны. Почти всякое слово случайно, и почти ни про одно этого не доказать. Неполнота перестаёт быть экзотикой на краю теории и становится её обычным состоянием, причём измеряемым — в битах.
Оговорка, без которой было бы нечестно. Сам Чейтин делал из своей теоремы далеко идущие выводы: математика-де по природе эмпирична, аксиомы надо добавлять, как в физике добавляют законы. С этим многие логики спорят, и по делу: постоянная $c$ зависит не от «силы» теории, а от того, как коротко записаны её аксиомы, — теория с тем же содержанием, но более лаконичной записью получит потолок ниже. Теорема верна; философия из неё выводится не так прямо, как хотелось автору.
Число Ω
Второй, более знаменитый результат — конкретное число. Сумма берётся по всем самоограниченным программам $p$, которые останавливаются:
$$\Omega \;=\; \sum_{p\,:\ \text{останавливается}} 2^{-|p|}$$
Это вероятность того, что наугад набранная программа когда-нибудь остановится: подбрасываем монету, получая бит за битом, пока не сложится осмысленная программа, и спрашиваем, встанет ли она.
Число $\Omega$ лежит между нулём и единицей и определено совершенно однозначно (для выбранной машины). А двоичная запись его — случайна в самом сильном смысле: $K(\Omega_{1..n}) \geqslant n - c$.
Почему так. Знай мы первые $n$ битов $\Omega$, мы решили бы проблему остановки для всех программ длины не больше $n$: запускаем все программы параллельно, накапливаем сумму от тех, что остановились, и ждём, пока накопленное не сравняется с известными нам битами; после этого ни одна короткая программа уже не остановится — иначе сумма превысила бы $\Omega$. Значит, $n$ битов $\Omega$ содержат в себе ответы на все вопросы об остановке короче $n$ — столько информации в $n$ битах уместиться может только при полной несжимаемости.
Определённое и непознаваемое
Вот в чём соль, и это стоит проговорить в классе. $\Omega$ — не «случайное число» в бытовом смысле. Его никто не бросал, оно не зависит от опыта, оно задано формулой и единственно. И тем не менее его нельзя вычислить: не существует алгоритма, выдающего его цифры.
Определённость и предсказуемость — не одно и то же. Ровно то же самое говорит про мир Пуанкаре, только здесь это доказано в чистой математике, где нет ни измерений, ни приборов, ни начальных данных.
Кое-что о $\Omega$ всё-таки известно. Для одной конкретной машины в 2002 году вычислили первые 64 бита. И известно, чего стоили бы следующие: выписана программа длиной 7780 битов, которая останавливается тогда и только тогда, когда гипотеза РиманаБернхард РиманПрожил тридцать девять лет и оставил около десяти работ — из которых выросли современная геометрия, теория функций комплексного переменного и главная нерешённая задача математики. ложна. Знай мы первые 7780 битов $\Omega$ — вопрос был бы закрыт. Знать их мы не будем.
Для класса
- Почему в сумме для $\Omega$ нужны именно самоограниченные программы? Что случится с суммой, если разрешить любые двоичные строки? (Подсказка: посчитайте $\sum 2^{-|p|}$ по всем строкам длины $n$.)
- Объясните своими словами, почему знание первых $n$ битов $\Omega$ решает проблему остановки для программ длины $\leqslant n$.
- Гёделево утверждение говорит о себе. Утверждение $K(x) > c$ ни о чём себя не говорит — это утверждение о конкретном слове. Почему же оно всё равно недоказуемо?
- У теории с более коротко записанными аксиомами потолок $c$ ниже. Значит ли это, что она слабее? Обсудите — и заодно то, почему из теоремы Чейтина труднее сделать философские выводы, чем кажется.
О человеке
Грегори Чейтин (род. 1947) вырос в Нью-Йорке, учился в Бронксской школе науки и первые свои работы об алгоритмической сложности написал школьником — печатать их начали, когда автору было восемнадцать. К понятию, которое сейчас называют колмогоровской сложностью, он пришёл третьим и совершенно независимо: Соломонов искал формализацию индукции, КолмогоровАндрей Николаевич КолмогоровДал вероятности аксиомы, турбулентности — закон, сложности — определение, а школьной математике в СССР — программу, по которой учились миллионы. — определение случайной таблицы, Чейтин — предел возможностей формальных систем.
Больше сорока лет проработал в исследовательском центре IBM в Йорктаун-Хайтс. Автор множества популярных книг, спорщик и человек резких формулировок: значительная часть написанного им — не теоремы, а полемика о том, чем математика является на самом деле.