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

Question

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

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

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

Благодарю.

Answer 1

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

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

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

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

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

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

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

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

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