Энтропия клеточных автоматов

[Lesobrod]

Вот попалась такая "демонстрация" на Wolfram Demonstrations:
http://demonstrations.wolfram.com/Cellu ... taEntropy/
У кого нет Wolfram на компе, может, вроде, скачать бесплатный плеер
и посмотреть онлайн. Собственно, смотреть там особо нечего.
Клеточный автомат - это обобщение игры "Жизнь". Начальная двоичная конфигурация на прямой или плоскости преобразуется по определенным правилам в новую. Ну, я надеюсь, тему все знают. А вот энтропия этих конфигураций, это любопытно. Автор демонстрации предлагает вычислять энтропию данного состояния по простейшей формуле:
$H=-N(black)*P(black)*log_2 P(black)-N(white)*P(white)*log_2 P(white)$.
Но если сравнить узоры, порождаемые по правилу, скажем, 23 и по правилу 165, то первый явно упорядочен, а второй гораздо более хаотичен. Между тем энтропия получается одинаковой.
Ну, по такой формуле она и будет одинаковой.
Но, может, есть более корректные способы вычисления энтропии как меры хаотичности?
В свое время интересовался эти вопросом и даже какбе понял, чем энтропия Колмогорова-Синая отличается от топологической. Но всё это относилось к динамике траекторий во времени; на статические конфигурации чето мозгов не хватает

[Pavia]

Цитата:

Но всё это относилось к динамике траекторий во времени; на статические конфигурации чето мозгов не хватает

Все просто в качестве параметра t возьми координату чёрной точки.

Вот для двухмерного случая надо подумать.

[Toucan]

Pavia в сообщении #437941 писал(а):

Все просто в качестве параметра t возьми координату чёрной точки.

Pavia, напоминаю: у нас на форуме принято обращение на "Вы".

[Lesobrod]

Toucan, Вы, пожалуйста, не придирайтесь (^_^),
ведь никаких грубостей не наблюдается!
Хоть кто-то ответил...
Конечно, меня беспокоит двумерный случай.
Если свести его к одномерному путем сканирования по строкам
и столбцам, то в смысле оценки порядка/хаоса явно многое
потеряется или исказится. Собственно, вопрос не мелкий и связан со многими приложениями - как корректно оценить меру хаотичности
двумерного бинарного массива? Догадываюсь, что полностью корректной
и замкнутой процедуры не существует; но любые соображения приветствуются!

[Circiter]

2Lesobrod

Цитата:

как корректно оценить меру хаотичности
двумерного бинарного массива?

В принципе, можно попробовать, ну например вычесть (поэлементно) из исходного массива (матрицы) его "сглаженную" версию, т.е. результат свертки с "гауссианом", а потом просуммировать ячейки. Это я к тому, что можно воспользоваться связью энтропии и количеством информации (в конечном счете, я предлагаю оценивать степень архивируемости узора-картинки; а для оценки этой величины ведь можно даже архиваторы типа winzip'а приспособить :) )...

[Lesobrod]

Circiter в сообщении #439803 писал(а):

2Lesobrod
ведь можно даже архиваторы типа winzip'а приспособить :) )...

Спасибо, вот это конструктивно!
Вообще, тема глубокая оказалась.
Нарисовал иконку 8х8 черно-белую с закономерностями;
в bmp заняла 246 байт, и ессессно 100% по узору. Сохранил в jpg.
100 едениц качества, черно-белый вариант тоже 100% сохранили узор,
но заняло 646 байт. Ниже качество занимает меньше места, но выдает
серые артефакты.
Упаковал в zip, уровень 9. Получилось 173 байта. Распаковалась отлично.
Игрался потом долго. Рекорд - 188 байт (против 246 в оригинале).
Я уверен, что это был совершенно случайный набор, и тем не менее,
удалочь передать его заметно меньшим количеством информации.

[Xaositect]

Ну заголовки BMP и DIB около 100 байт занимают ЕМНИП, так что на таких объемах будет сильно влиять.
Экспериментируйте с чистыми данными, без служебной информации.

[Circiter]

2Lesobrod
Может быть вас это заинтересует, H.Zenil, Compression-based investigation of the dynamical properties of cellular automata and other systems (arXiv:0910.4042v4 [cs.CC]).

[Lesobrod]

Спасибо!
Мужик серьёзно подошёл к вопросу.
Меня вот что еще интересует. Допустим, есть некий алгоритм
типа клеточного автомата или "хаотических" преобразований
Фейгенбаума, пекаря и т.п. Возможны как минимум два подхода
к оценке степени хаотичности (любым методом).
1. Анализ только конечного состояния.
2. Анализ всей последовательности состояний.
Например, если начать игру "Жизнь" со случайно заполненного поля,
уже на втором шаге получится структура, т.е. энтропия будет падать
(кстати, предел как-то можно оценить?..)
Я наблюдал и обратную картину, когда заполненное в шахматном порядке поле одним из автоматов превращалось в хаос (по виду, а количественно еще надо оценить).
Вот ищу материалы на эту тему..