Элементарные клеточные автоматы. 1. Код Вольфрама и эволюция автомата
Элементарный клеточный автомат — это одномерный автомат, клетки которого принимают только два значения: 0 (белый) и 1 (черный).
Как и в широкоизвестной игре Жизнь, новое состояние каждой клетки определяется ее соседями: левым, правым и ей самой.
Но игра Жизнь — это двумерный автомат, развитие которого происходит на плокости. Поэтому на новое состояние клетки в Жизни влияет восемь соседей.
Элементарный КА — это одномерный автомат, развивающийся в полосе. Поэтому на новое состояние клетки влияют только два ее соседа.
Код Вольфрама
Новое состояние [b] клетки [a] определяет триплет
где [a-1] и [a+1] левая и правая соседняя клетка.
Так как любой триплет состоит только из нулей и единиц, то он является двоичной записью трехбитного числа от 0 до 7. Всего мы можем построить восемь уникальных триплетов:
111 110 101 100 011 010 001 000
Каждому триплету сопоставим правило, которое переводит центральную клетку в следующее состояние:
111 → 0 110 → 0 101 → 0 100 → 0 011 → 0 010 → 0 001 → 1 000 → 0
111 → 0 110 → 0 101 → 0 100 → 1 011 → 1 010 → 1 001 → 1 000 → 0
В итоге восемь триплетов сгенерируют восьмибитное число, полностью описывающее поведение клеточного автомата:
Отсюда следует, что любому восьмибитному числу от 0 до 255 соответствует единственный элементарный клеточный автомат, правила которого полностью описывает битовое представление этого числа. То есть существует ровно 256 элементарных клеточных автоматов.
Такой способ обозначения клеточных автоматов называется Кодом Вольфрама.
Код Вольфрама — это запись правил развития (эволюции) элементарного клеточного автомата в виде числа от 0 до 255.
Запись правил была предложена Стивеном Вольфрамом в статье 1983 года Statistical mechanics of cellular automata.
Эволюция элементарного клеточного автомата
Эволюция ЭКА начинается с произвольной конфигурации черных и белых клеток.
Но для наглядности, в качестве начальной конфигурации часто используют единственную черную клетку.
Клетка генерирует черно-белый узор, согласно заданному правилу.
Узор показывает пошаговое развитие КА.
Каждая строка — это состояние КА на данном шаге.
Автомат развивается сверху вниз.
Начальное состояние — самая верхняя строка узора.
Если начать развитие КА со случайной черно-белой полосы, получится более красивый паттерн.
Развитие автомата может идти до бесконечности или довольно быстро завершиться.
В следующий раз рассмотрим классы и преобразования элементарных клеточных автоматов.