Способы измерения сложности последовательности бит

Question

Я ищу простой способ оценить сложность последовательности бит фиксированного размера (вероятно, максимальной длины 10). Например, я полагаю, что 0000000 и 111111 не очень сложны, но 101010 и 101101 находятся в другом месте спектра.

Я знаю, что сложность Колмогорова невыполнима, но возможно ли, что его можно запрограммировать просто для последовательностей фиксированной (и малой) длины с бинарным алфавитом? Или есть еще одна мера, которая может только приблизить меру, но намного легче вычислить?

Важно, чтобы эта мера была довольно простой, чтобы я мог объяснить ее другим (хотя и достаточно образованным) людям.

Спасибо.

Answer 1

У вас должна быть процедура подсчета сложности, и нет лучшей процедуры.

Например, вы можете запустить код в строке и подсчитать количество прогонов.

Вы можете запустить строку через компрессор LZW (например, ZIP) и сообщить размер сжатого файла.

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

Например, вы можете попробовать сначала инвертировать каждый бит, а затем попробовать запустить кодировку. Или попробуйте инвертировать биты 2 и 3, затем бит 6 и 7 и так далее.

Это возможные способы получения меры, но это все, что они есть.

Сложность Колмогорова - это размер самой маленькой программы, в битах, которая может воспроизводить строку, и это зависит от языка (будь то машина высокого уровня, сборки, машины или машины, или код для управления специальным которую вы создали для этой цели).

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

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