Элементарные клеточные автоматы. 2. Преобразования инверсии и отражения
Элементарный клеточный автомат можно преобразовать в новый автомат, который построит идентичный узор. Для этого следует изменить правила исходного автомата с помощью инверсии, отражения или инверсии с отражением. Такие преобразования называются простыми.
Простые преобразования клеточных автоматов
Кажется, что в простых преобразованиях нет ничего сложно: инвертировал битовую запись правила или отразил ее слева-направо и готово. Но не тут-то было — такие очевидные решения работать не будут. Преобразования правил элементарных клеточных атоматов нужно выполнять по другому.
Давайте рассмотрим как следует преобразовать правила ЭКА и, заодно, потренируемся работать с битами.
Инверсия
Обычная инверсия изменяет биты правила автомата на противоположные: 0 ↔ 1. По идее это должно привести к инверсии генерируемого автоматом узора. Проверим, так ли это.
Инвертируем его биты, получив автомат 137:
Правило инвертировано, а узор нет. Попробуем еще раз.
И снова инвертируем его биты, получив автомат 130:
Опять получился совсем другой узор.
Для инверсии правила элементарного КА следует инвертировать не готовое правило, а тройки битов, которые его порождают. Вот так:
То есть первый шаг инверсии будет заключаться в зеркальной перестановке битов относительно центра правила. Однако этого мало: после зеркальной перестановки биты следует инвертировать.
Для инверсии элементарного клеточного автомата необходимо поменять местами следущие биты: 0 ↔ 7, 1 ↔ 6, 2 ↔ 5, 3 ↔ 4, затем инвертировать полученное число.
Возьмем автомат 118 и зеркально поменяем местами его биты:
118 = 0111 0110 ↔ 0110 1110 = 110
затем инвертируем полученное число:
110 = 0110 1110 ↔ 1001 0001 = 145
Правило сработало: 118 инверсия 145.
Проверим еще раз на автомате 125:
125 = 0111 1101 ↔ 1011 1110 = 190 ↔ 0100 0001 = 65
Получилось то, что было нужно: 125 инверсия 65.
Возьмем автомат 54 и построим его эволюцию:
Теперь отразим битовую запись 54, получив автомат 108 =
Однако после такого отражения построенная текстура совсем не походит на исходную. Почему? Потому что нужно отражать генерирующие тройки битов.
При таком отражении симметричные тройки останутся теми же, а несимметричные обменяются местами: 6 ↔ 3, 4 ↔ 1.
Для зеркального отражения элементарного клеточного автомата необходимо поменять местами следущие биты его правила: 6 ↔ 3, 4 ↔ 1.
В этом случае автомат 54 = 0011 0110 превратится в самого себя: 54 ↔ 54. Правило выполнено, но пример неудачый.
Возьмем не менее приятный автомат 193 =
Отразим его, переставив биты согласно правилу. Получим атомат 137 =
Видно, что сгенерированная текстура зеркально отразилась: 193 ↔ 137.
После перестановки битов превращается в автомат 89 =
Как видим, правило отражения работает правильно.
Инверсия + отражение
Теперь вы, вооруженные знаниями о манипуляциях с битами, самостоятельно сможете вывести правило, которое позволит получить отраженный инвертированный клеточный автомат. А мне остается подсчитать количество уникальных ЭКА.
Уникальные элементарные клеточные автоматы
Среди 256 элементарных клеточных автоматов, некоторые автоматы эквивалентны друг другу, так как генерируют одинаковые текстуры, отличающиеся только инверсией или отражением.
Тогда возникает закономерный вопрос: сколько всего существует уникальных элементарных клеточных автоматов, из которых можно построить все остальные автоматы?
Не вдаваясь детали, скажу, что их ровно 88 штук — в три раза меньше общего количества ЭКА.
Из 256 элементарных клеточных автоматов только 88 являются уникальными, остальные эквивалентны друг другу с точностью до симметрии или отражения.