Приложения клеточных автоматов

В мире клеточных автоматов имеется класиификация (S. Wolfram, 1983), согласно которой все автоматы делятся на четыре класса, в зависимости от типа динамики изменяющихся состояний. Автоматы первого класса по истечении конечного времени достигают однородного состояния, в котором значения всех элементов одинаковы и не меняются со временем. Ко второму классу автоматов относятся системы, приводящие к локализованным структурам стационарных или периодических во времени состояний элементов. Третий класс составляют автоматы, которые с течением времени посещают произвольным (непериодическим) образом все возможные состояния элементов, не задерживаясь ни в одном из них. И, наконец, четвертый класс составляют автоматы, характер динамики которых зависит от особенностей начального состояния элементов. Некоторые начальные состояния приводят к однородному вырождению автомата, другие - к возникновению циклической последовательности состояний, третьи - к непрерывно меняющимся (как “по системе”, так и без видимой системы) картинам активности элементов.

К автоматам четвертого типа относится знаменитая игра “Жизнь” Дж. Конвея. Жизнь - это бесконечное плоское клеточное поле, состоящее из пустых клеток и организмов. Развитие любой конфигурации определяют 2 закона:

1. организм выживает, если имеет 2 или 3 соседей и умирает в противоположном случае;

2. новый организм рождается, если число соседей равно 3.

Существует следующая классификация разнообразных конфигураций:

1. Вырождающиеся

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

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

2. Стационарные

Из 4 организмов собираются стационарный, т.е. вечно живущий и не изменяющийся во времени ансамбль: блок.

При большем числе организмов появляется огромное количество стационарных конфигураций (или, как говорят, "натюрмортов"): бадья, лодка, корабль, змея, длинная змея.

...улей, каравай, пруд, длинная лодка, длинный корабль…

...баржа, рыболовный крючок, шляпа, авианосец...

...соты, тонущий корабль, дубинка, длинная баржа и т.д.

3. Периодические

Периодические колонии ("осцилляторы"): бакен, часы, жаба

...восьмерка, пентадекатлон, тумблер...

...пульсар, бриллиантовое кольцо, вертушка и т.д

4. Периодические со сдвигом (глайдер)

Но особенно интересен глайдер,

Состоящий из 5 «элементарных» организмов. Эта конфигурация не только периодически меняет свою форму, но и смещается на плоскости, двигаясь по диагонали. Есть в игре Life объекты, способные передвигаться и в горизонтальном направлении. Это так называемые космические корабли.

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

Большинство колоний относительно недолговечны. После нескольких десятков, от силы сотен поколений жизнь на клеточном поле прекращается, оставив после себя набор мигалок, блоков, ульев и прочих «останков», да еще какое-то количество глайдеров стремительно удаляется прочь от погибшей клеточной цивилизации в тщетной надежде наткнуться на что-то в пустом клеточном космосе. Поэтому всегда интересны колонии, способные жить долго, особенно если их исходное состояние достаточно малочисленно. Из таких долгожителей наиболее известны r-пентамино - 1103 поколения и желудь - 5206 поколений (на рис. показаны начальные конфигурации).

Список литературы

1. Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991.

2. фон Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.

3. Шалыто А., Туккель Н. От тьюрингова программирования к автоматному Мир ПК. 2002, №2.

4. Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. М.: 1973.

5. Федотьев А. Клеточный автомат – http://rain.ifmo.ru/~fedotiev/

6. Мир, который построил Конуэй http://www.beluch.ru/life/conway.htm