Клеточные автоматы и игра «Жизнь»
Игра Конвея "Жизнь" - типичный пример клеточного автомата, как математического объекта, представляющего собой дискретную динамическую систему. По существу клеточные автоматы являются синтетическими мирами, поведение которых большей частью определяется простыми локально действующими правилами. В этих мирах пространство представляет собой равномерную сетку, каждая ячейка которой (клетка) содержит информацию о своем состоянии. Время - дискретно. Законы такого мира представляют собой небольшое количество правил, основные из которых описываются таблицей переходов, по которой клетка вычисляет свое новое состояние на каждом такте (минимальный отрезок времени) на основе своего состояния и состояний ее соседей.
Клеточный автомат можно рассматривать как упрощенный локальный вариант рекурентной нейронной сети. Обладая простотой и наглядностью, он позволяет понять основные особенности параллельного алгоритма. Рассматривая клеточные автоматы с этой точки зрения, необходимо отметить, что клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных взаимозависимостей состояний таких систем. Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных; законы развития выражаются единственным набором правил, по которой любая клетка на каждом шаге вычисляет свое новое состояние по состояниям ее близких соседей. Если задан подходящий набор правил, то такой простой операционный механизм достаточен для поддержания целой иерархии структур и явлений. Клеточные автоматы дают полезные модели для многих исследований в естественных науках. Они образуют общую парадигму параллельных вычислений, подобно тому, как это делают машины Тьюринга для последовательных вычислений.
Примеры развития колоний в игре "Жизнь"
Хорошим примером для ознакомления с принципами работы клеточного автомата является игра Джона Конвея "Жизнь". Индивидуум этой популяции представлен клеткой в состоянии 1, в то время как клетка в состоянии 0 представляет пустое пространство (для образности можно говорить о "живых" и "мертвых" клетках). Мерой течения времени служит смена поколений колонии, которая происходит по известным правилам.
Популяция (или колония) клеток в "Жизни" может все время расти, непрерывно меняя свое расположение, форму и число клеток. Однако чаще колония становится в конце концов стационарной или циклически повторяет один и тот же конечный набор состояний. Длина цикла называется периодом колонии. Пример развития колонии показан на рис. "Примеры развития колоний в игре "Жизнь". Номер поколения увеличивается слева направо. Верхний ряд представляет осциллирующий триплет, так называемый блинкер. Конфигурация, становящаяся стабильной на третьем шаге, изображена в среднем ряду. В нижнем ряду представлена более сложная конфигурация, сначала растущая до седьмого шага, а затем распадающаяся на четыре блинкера.
На основе этого примера можно сформулировать общие правила построения клеточных автоматов:
- Состояние клеток дискретно (обычно 0 и 1, хотя могут быть автоматы и с большим числом состояний).
- Соседями являются ограниченное число клеток, часто это ближайшие клетки.
- Правила, задающие динамику развития клеточного автомата, обычно имеют простую функциональную форму и зависят от решаемой проблемы.
- Клеточный автомат является тактируемой системой, т.е. смена состояний клеток происходит одновременно.
- Клеточные автоматы предоставляют большую свободу в выборе структуры и правил развития системы. Это позволяет моделировать на их основе или решать с их помощью самые разнообразные задачи.
Клеточные автоматы широко применяются для моделирования систем, для которых существенно пространственное взаимодействие между элементами системы. Существует много примеров таких моделей в биологии, информатике (включая системы телекоммуникации) и др. областях. В физике клеточные автоматы примененяются для анализа явлений переноса (теплопроводности, диффузии и вязкости), моделирования твердого тела.
