Шутки и не шутки про порядок и хаос

[epros]

Anton_Peplov, на этом форуме уже не впервые упоминается колмогоровская сложность как якобы однозначно определённая реально вычислимая метрика и на основании этого делаются выводы, что строки типа $111 \ldots 1$ якобы имеют "объективно" более низкую сложность, чем, скажем, те, которые выдаёт генератор случайных чисел. Однако на самом деле понятие сложности совершенно субъективно, то бишь зависимо от тех инструментов (грамматик), которыми мы пользуемся для генерации строк.

Я могу это проиллюстрировать следующим образом. Вот код генератора строки:

for (int i=0; i<100500; i++) {String[i]=f(i)}

где функция $f(i)$ в Вашем случае определена как константа, равная единице. А в моей библиотеке - это некая хэш-функция. И если в Вашем случае мы получим длинную строку из единиц, то в моём случае мы получим псевдослучайную последовательность, которую трудно будет распознать как нечто "простое". Тем не менее, код для генерации моей строки столь же прост.

[mihaild]

Anton_Peplov в сообщении #1695860 писал(а):

для которой количество строк в напечатанном тексте программы превзойдет длину последовательности

А с чего вдруг строк? Надо в битах считать. Любую последовательность можно напечатать программой из одной строки.
epros говорит об очевидной вещи. Пусть $f$ - инъективная функция из строк в строки. Тогда количество строк длины до $n$, которые она укорачивает, $\|\{x: |x| \leq n \wedge |f(x)|<|x|\}|$, не меньше чем количество строк длины до $n$, которые она удлиняет, $\|\{x: |x| \leq n \wedge |f(x)|>|x|\}|$.
Архиваторы всё равно бывают полезны, потому что можно сделать так, чтобы никакая строка не удлинялась сильно, но некоторые строки сильно укорачивались.

Но говорить о колмогоровской сложности конкретной последовательности ИМХО всё равно не очень хорошо. Можно говорить только об асимптотике. Понятно, что $K(1^n) \leq \log n + O(1)$. Но константа может быть какой угодно. И про соотношениек $K(1^{\text{длина генома человека}\|})$ и самой этой длины - ничего нетривиального сказать нельзя.

epros в сообщении #1695867 писал(а):

то бишь зависимо от тех инструментов (грамматик), которыми мы пользуемся для генерации строк

Всё-таки МТ это довольно универсальный инструмент. И асимптотически колмогоровская сложность строк, сгенерированных вашим способом, естественно, всё та же самая $K(n) + O(1)$.

[epros]

mihaild в сообщении #1695868 писал(а):

Всё-таки МТ это довольно универсальный инструмент.

Это понятно. Но для МТ без разницы записана ли на ленте последовательность из $100500$ единиц или такой же длины псевдослучайная последовательность: и ту, и другую можно сгенерировать очень похожими по сложности программами. Но вот, не зная формулы хэш-функции, угадать её в целях "сжатия" данной последовательности - практически невозможно. А константа, подставленная вместо этой хэш-функции, по неким субъективным причинам угадывается легко.

[Mihaylo]

Anton_Peplov в сообщении #1695848 писал(а):

последовательность $111111\dots 1$ кодируется двумя командами "напечатать 1 - повторить $n$ раз" (сложность $2 + C$)

Ещё раз повторю, что вы выбрали язык удобный. Бывают неудобные. И тут вся эта колмогоровская сложность летит в тартарары.

Нужно чётко определить язык и только после этого оценивать длину кодирующей последовательности. А так - это всё теория про какой-то мощный итеративный язык типа МТ.

-- 30.07.2025, 16:59 --

Самый мощный язык - это тот, который генерирует нужную последовательность одной командой и другой последовательности генерировать не требуется. Это можно назвать полным соответствием задачи и решателя.

[Anton_Peplov]

mihaild в сообщении #1695868 писал(а):

А с чего вдруг строк? Надо в битах считать. Любую последовательность можно напечатать программой из одной строки.
epros говорит об очевидной вещи. Пусть $f$ - инъективная функция из строк в строки. Тогда количество строк длины до $n$, которые она укорачивает, $\|\{x: |x| \leq n \wedge |f(x)|<|x|\}|$, не меньше чем количество строк длины до $n$, которые она удлиняет, $\|\{x: |x| \leq n \wedge |f(x)|>|x|\}|$.

Да, тут я сглупил, прошу прощения. Пример с программой на C# иррелевантен. Спорить с теоремами - не мой стиль.

epros в сообщении #1695867 писал(а):

колмогоровская сложность как якобы однозначно определённая реально вычислимая метрика

А вот этого я, извините, не говорил. Это Вы уже домысливаете.

Колмогоровская сложность однозначно определена, только когда фиксирован оптимальный декомпрессор. Колмогоровская сложность двоичного слова $x$ невычислима, это тоже теорема. Но при фиксированном оптимальном декомпрессоре вычислимы верхние оценки на колмогоровскую сложность относительно этого декомпрессора. Хотя бы одну точно получим. Запустим оптимальный декомпрессор $D$ диагонально по двоичным словам возрастающей длины: сделаем первый шаг $D(0)$, первый шаг $D(1)$, второй шаг $D(0)$, второй шаг $D(1)$, первые два шага $D(01)$ и т.д. Для всех слов $y$, для которых выполнение $D(y)$ уже завершилось, проверяем, получилось ли $x = D(y)$. Поскольку для оптимального декомпрессора всякое слово имеет описание, рано или поздно мы распакуем $x$ из какого-нибудь описания $y$ - правда, это будет не обязательно кратчайшее описание, а лишь описание, распаковка которого потребовала меньше всего шагов диагонального алгоритма. Тем не менее $|y|$ будет верхней оценкой колмогоровской сложности слова $x$. И поскольку мы начинаем распаковку с самых коротких потенциальных описаний, при разумном выборе декомпрессора можно ожидать, что эта оценка будет не слишком завышенной. В простых примерах типа $111\dots$ хорошие оценки сверху легко получить вообще "на пальцах".

Да, выбор декомпрессора равносилен выбору языка. Да, сложность любой последовательности зависит от языка. И что? Весь процесс познания в той или иной степени зависит от языка.

Вот как я бы оценивал колмогоровскую сложность двоичных слов, если бы мне это понадобилось. Фиксируем удобный нам язык (равно оптимальный декомпрессор) и в нем оцениваем сверху колмогоровскую сложность любых слов. Если за разумное время не нашли оценки ниже чем длина слова, считаем, что сложность сравнима с длиной (на аддитивную константу плевать, мы можем ее директивно занулить). Это в любом случае будет так для абсолютного большинства слов. Доказано, что доля слов сложности меньше $n - m$ среди всех слов длины $n$ составляет меньше $2^{-m}$ . Например, доля слов сложности менее 90 среди всех слов длины 100 меньше $2^{-10}$. Хорошо сжимаемые слова - это капля в море при любом выборе языка. Просто для разных языков эти капли будут разными.

Вот такой инструментальный подход. А разговоры про объективность предлагаю оставить философам.

[mihaild]

Anton_Peplov в сообщении #1696206 писал(а):

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

И будем промахиваться сколь угодно сильно.
Вообще, невычислима не только колмогоровская сложность, но и нетривиальные нижние оценки на неё. Т.е. если у нас есть частично вычислимая функция $f$, такая что если она останавливается на $x$, то $f(x) \leq K(x)$, то $f$ ограничена сверху некоторой константой.

[Anton_Peplov]

mihaild в сообщении #1696282 писал(а):

Вообще, невычислима не только колмогоровская сложность, но и нетривиальные нижние оценки на неё.

Разумеется. Так и доказывается невычислимость самой колмогоровской сложности (по крайней мере, у Верещагина и К).

mihaild в сообщении #1696282 писал(а):

И будем промахиваться сколь угодно сильно.

Конечно, для достаточно большого $n$ и, наверное, любого $m < n$ найдется такое слово $|x|=n$, что абсолютная ошибка в оценке $K(x)$ составит $m$. Но чем больше ошибка, тем реже она будет встречаться. Это так даже для тривиального алгоритма "оценка сложности слова всегда равна его длине", причины я озвучивал выше. И чем больше время, которое мы готовы отвести диагональному алгоритму, тем реже будет встречаться относительная ошибка на $m/n$. Предполагаю, что если нас интересуют только слова длины $n<N$, то частоту относительных ошибок на фиксированную величину $m/n$ можно довести до сколь угодно низкого уровня.

[epros]

Anton_Peplov в сообщении #1696206 писал(а):

А вот этого я, извините, не говорил. Это Вы уже домысливаете.

Зачем тогда вообще говорить о том, чтобы применять для оценки конкретных слов эту самую колмогоровскую сложность? У нас либо есть конкретная формула для расчёта численного значения сложности заданного слова, либо её нет. Если есть, то предъявите конкретную формулу. А абстрактно ссылаться на "колмогоровскую сложность", это всё равно что рассказывать, что у нас есть формула для преобразования одного шара в два такие же.

Anton_Peplov в сообщении #1696206 писал(а):

Да, выбор декомпрессора равносилен выбору языка. Да, сложность любой последовательности зависит от языка. И что? Весь процесс познания в той или иной степени зависит от языка.

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

Давайте я Вам опишу свой алгоритм сжатия. Берём $255$ разных хэш-функций $hs_i:\mathbb N \to \{0,1\}$, где $i$ - номер хэш-функции от $1$ до $255$. Если исходный файл длиной $100500$ бит совпадает с последовательностью значений функции $hs_i(j)$ для всех $1 \le j \le 100500$, то в сжатый файл пишем один байт, кодирующий число $i$. Если не совпадает, то в сжатый файл пишем нулевой байт (восемь нулевых битов), после которого дописываем исходную последовательность из $100500$ бит. Итак, $255$ из $2^{100500}$ возможных исходных слов сожмутся в $1$ байт, а остальные $2^{100500}-255$ исходных слов расширятся на один байт. Алгоритм декомпрессии очевиден, обо определён алгоритм компрессии без потери информации. Заданный "язык" - это и есть определения этих $255$ хэш-функций. "Сложность" последовательности из $100500$ бит применительно к этому языку составляет $8$ бит для $255$ сжимаемых последовательностей и $100508$ бит для остальных $2^{100500}-255$ несжимаемых последовательностей. "Сложность" последовательности из $100500$ единиц странным образом составит $100508$ бит, насколько бы она ни казалась нам "простой" с точки зрения банальной эрудиции.