Альтернативное док-во теоремы Колмогорова-Соломонова.

[Pulseofmalstrem]

Доброе время суток!
На днях придумал новое для себя доказательство теоремы Колмогорова-Соломонова о существовании оптимального способа описания, и мне хотелось бы проверить его корректность.

Для начала дадим несколько определений, чтобы уточнить термины. Далее будем считать, что $\Sigma$ -некоторый конечный алфавит, а
$\Sigma^{*}$ - словарное пространство над ним, всякую вычислимую функцию $D: \Sigma^{*} \to \Sigma^{*}$ будем называть способом описания, причем если $D(x) = y$, то говорим, что $x$ есть описание $y$ относительно $D$

Сложностью слова $x$ относительно способа $D$, как и обычно, называем длину кратчайшего описания $x$ относительно $D$, и обозначаем $KS_D(x)$

Говорим, что способ описание $D_1$ не хуже способа $D_2$ ($D_1 \geqslant D_2$), если существает такая константа $C$, что $\forall w \in \Sigma^{*} \to KS_{D_1}(w) \leqslant KS_{D_2}(w) + C$

И теорема Колмогорова-Соломонова звучит так:
Сущесвует способ описания, который не хуже всех остальных.

Доказательство:

Рассмотрим множество $F$ всех вычислимых функций $f: \Sigma^{*} \to \Sigma^{*}$, и введем на нем отношение частичного порядка:
$f \geqslant g$, если $f$ не хуже $g$, ясно что это частичный порядок на множестве $F$, докажем что всякикое линейно упорядоченное подмножество в $F$ имеет максимальный элемент:
Пусть это не так, и $\Lambda$ - линейно-упорядоченное подмножество, в котором нет максимального элемента, тогда можно выписать цепочку неравенств:
$D_1 \leqslant D_2 \leqslant \dots\ \leqslant D_n \leqslant \dots$
Или раскрывая буквально:
$\forall w \in \Sigma^{*} \to KS_{D_1}(w) + C_1 \geqslant KS_{D_2}(w) + C_2 \geqslant \dots$
Подставив в это неравенство любое слово мы получим бесконечно убывающую последовательность натуральных чисел, что невозможно, значит в любом линейно упорядоченном множестве есть максимальный элемент, а тогда по лемме Цорна в $F$ есть максимальный элемент, который и будет оптимальным способом описания.

P.S. Естественно мы полагаем, что два способа описания равны, если они оба не хуже друг друга, вопрос в том не сделано ли каких-либо ошибок.

[mihaild]

Pulseofmalstrem в сообщении #1166787 писал(а):

Или раскрывая буквально:
$\forall w \in \Sigma^{*} \to KS_{D_1}(w) + C_1 \geqslant KS_{D_2}(w) + C_2 \geqslant \dots$

Вот это вы непонятно как получили.
Мы имеем $KS_{D_i}(w) + C_i \geqslant KS_{D_{i+1}}(w)$. Или, перенося константу в другую часть, $KS_{D_1} \geqslant KS_{D_2} - C_1 \geqslant KS_{D_3} - C_1 - C_2 \geqslant \ldots$.

-- 07.11.2016, 13:41 --

Вообще, вы в доказательстве нигде не пользовались вычислимостью декомпрессора, так что оно без изменений переносится на вообще все возможные функции, чего быть не может (в множестве всех декомпрессоров универсального не существует, т.к. можно было бы рассмотреть декомпрессор, разжимающий $n$ в строку, имеющую сложность $2^n$ относительно универсального).

[Pulseofmalstrem]

mihaild
Рассматрим начало цепочки (аргумент буду опускать):
$KS_{D_1} +C_1 \geqslant KS_{D_2}$
$KS_{D_2} + C_2 \geqslant KS_{D_3}$
Прибавим в первому неравенству константу $C_2$
$KS_{D_1} + C_1 +C_2 \geqslant KS_{D_2} + C_2 \geqslant KS_{D_3}$ (второе неравенство из второй строчки)
Если теперь обозвать $C_1 +C_2 = C'_1$
То мы придем к строчке:
$KS_{D_1} + C'_1 \geqslant KS_{D_2} + C_2$
Проделав так по индукции получим ту самую цепочку.

[mihaild]

Pulseofmalstrem в сообщении #1166795 писал(а):

Проделав так по индукции получим ту самую цепочку.

Получим подобную цепочку любой конечной длины. Но дополнительное слагаемое в левой части растет с ростом длины цепочки, так что бесконечную цепочку получить не получится.

[Pulseofmalstrem]

В лоб и вправду просто так не докажешь, но интересно можно ли попробовать все-таки воспользоваться леммой Цорна.

[mihaild]

Может и можно (сходу не придумал), но любое доказательство должно существенно использовать вычислимость. А еще бывают цепи, устроенные не как $\omega$.