lection12.tex

Теорема Гёделя о неполноте арифметики показывает недоказуемость некоторого крайне абстрактного и 
оторванного от земли выражения. А есть ли недоказуемые выражения, которые имеют практический смысл?

\begin{definition}Колмогоровской сложностью $K(x)$ натурального числа $x$ мы назовем 
минимальную длину (в битах) записи рекурсивной функции (в кодировке ASCII, в синтаксисе,
использованном в данном конспекте; вместо символа $\mu$ мы будем использовать $M$), 
вычисляющей данное число.
\end{definition}

Легко видеть, что $K(x) \le 8\cdot(5x + 1)$: каждое число мы можем представить, как
$S \langle N, S \langle N, \dots S \langle N,Z \rangle \rangle \rangle$.
Однако, минимальную длину колмогоровской сложности нам будет найти затруднительно 
в силу следующей теоремы:

\begin{theorem}Теорема Чайтина о неполноте. Существует такое число $L$ (вообще говоря,
зависящее от конкретного абстрактного алгоритма, способа записи и т.п.), что
ни для какого числа $x$ нет способа доказать в формальной арифметике, что 
$K(\overline{x}) > L$.
\end{theorem}

\begin{proof}
Наметим доказательство. Сразу заметим, что полностью формальное его изложение несколько более
сложно и требует дополнительных понятий.

Во-первых, введем 
\end{proof}

Данная теорема --- еще один вариант доказательства теоремы Гёделя о неполноте арифметики. 
В самом деле, всего чисел, имеющих длину записи, меньшую $L$, меньше, чем $2^0+2^1+\dots+2^L=2^{L+1}$.
Значит, неизбежно найдётся такое число $x$, что $K(x) > L$. Однако, показать
$\vdash K(x) > L$ мы не можем, при том, что это верное утверждение.