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

[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 --

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