EcoSimulation — 07. Модели на основе клеточных автоматов

 

Д.А. Шабанов
Конспект курса
"
Имитационное моделирование сложных биосистем
(с использованием LibreOffice Calc)
"

Подбор параметров и поиск решения Модели на основе клеточных автоматов Примеры разнообразных моделей, их замысел и дизайн
Имитационное моделирование биосистем-06 Имитационное моделирование биосистем-07 Имитационное моделирование биосистем-08

 

7. Модели на основе клеточных автоматов

7.1. Игра «Жизнь» Джона Конвея

Игра «Жизнь» была создана Джоном Конвеем в 1970 г. Она явилась вариантом реализации идеи двух классиков кибернетики: Алана Тьюринга и Джона фон Неймана. Чтобы понять значение этой игры, нужно пройти по основным вехам ее предыстории. 

Машина Тьюринга, предложенная в 1936 году, – это абстрактный исполнитель, который выполняет определенный алгоритм, переходя из одного состояния в другое. Идея Тьюринга состояла с том, что управляющее устройство, способное находится в конечном количестве состояний, выполняя определенные алгоритмы, способно обеспечить все используемые человечеством последовательности действий.

Фон Нейман пытался реализовать идею алгоритмической машины Тьюринга с помощью клеточного автомата. Клеточным автоматом называется регулярная структура из ячеек, каждая из которых может находится в одном из конечного множества состояний. Для работы клеточного автомата требуется задать его начальное состояние и правила перехода ячеек из одного состояния в другое.

Машина фон Неймана – это машина Тьюринга, способная воспроизводить сама себя. В 1950 году фон Нейману удалось реализовать эту машину на пространстве из 200 000 клеток, каждая из которых могла находится в 29 состояниях. Правила перехода каждой клетки из одного состояния в другое зависели от состояний четырех соседних клеток. После создания первой машины фон Неймана удалось создать ее значительно более простые реализации (требующие меньшее количество ячеек и меньшее количество состояний). В какой-то степени упрощение машины фон Неймана стало одним из интеллектуальных упражнений для кибернетиков. В русле этой работы и была создана описываемая здесь игра. Она, конечно, не реализует машину фон Неймана, но является способом изучения свойств клеточных автоматов, управляемых простыми правилами.

Математик Джон Конвей в 1970 году опубликовал в журнале Scientific American (в рубрике «Математические игры», которую вел известный популяризатор Мартин Гарднер) описание игры «Жизнь». Ее правила чрезвычайно просты (и этим, в частности, определяется ее притягательность).

Игра реализуется на плоскости, состоящей из квадратных клеток. Каждая клетка имеет восемь соседей (считая тех, с которыми она соприкасается уголками). Каждая клетка может находится в двух состояниях: «живом» (занятом, обычно показываемом черным цветом) и «мертвом» (свободном, белом). Для запуска игры надо создать начальную конфигурацию («первое поколение»).

Каждое следующее поколение определяется предыдущим с учетом двух правил:
– «мертвая» клетка, имеющая трех «живых» соседей, становится «живой»;
– «живая» клетка, имеющая менее двух или более трех «живых» соседей, становится «мертвой».

Вычислять следующие поколения имеет смысл, пока на поле остаются «живые» клетки или пока система не входит в цикл, повторяя одно из своих предыдущих состояний.
Этих правил достаточно для порождения множества паттернов (фигур), демонстрирующих сложное поведение. Многие конструкции из клеток быстро деградируют. Некоторые оказываются устойчивыми (как, например, квадрат из четырех соседних клеток). Существуют «планеры» («gliders») – паттерны, способные циклически менять свою конфигурацию, неограничено перемещаясь по плоскости. 

Изначально Конвей предполагал, что паттерн, способный обеспечивать неограниченное продолжение игры и бесконечно увеличивающееся количество живых клеток (естественно, при использовании бесконечной плоскости для игры) в этой игре невозможен. Конвей не мог доказать это утверждение и предложил премию за его доказательство или опровержение. Премию получила группа хакеров под руководством Билла Госпера: они в течение полутора лет пытались создать паттерн, который воспроизводил бы сам себя, порождая при этом другие фигуры. На применяемом для описания игры «Жизнь» жаргоне речь идет о создании «пушки», стреляющей «планерами».

«Планерная пушка Госпера» стала первым паттерном, способным существовать неограниченно долго и порождать неограниченное количество «живых» клеток.
Конечно, особой необходимости реализовывать игру «Жизнь» средствами Calc нет: существует множество ее хороших реализаций. Например, на этом сайте можно как испробовать любые свои начальные конфигурации, так и увидеть множество фигур, имеющих свои названия, в том числе – «пушку Госпера», «Gosper gun». Однако, поскольку для решения биологических проблем может быть полезно использование клеточных автоматов, созданных средствами Calc, принципы создания таких моделей проще всего обсудить на примере игры «Жизнь» (рис. 7.1).

Рис. 7.1. «Планерная пушка Госпера» в реализации игры Конвея «Жизнь», выполненной в Calc

7.2. Реализация игры «Жизнь» в Calc

Рассмотрим пример реализации игры «Жизнь», выполненный в Calc. Его можно скачать, но лучше сделать самостоятельно. Все, что для этого необходимо, описано далее.

Рис. 7.2.

СТРАНИЦА В РАЗРАБОТКЕ!

Рис. 7.3.

 

Рис. 7.4.

 

Рис. 7.5.

 

Рис. 7.6.