В статье автор исследует эволюцию клеточного автомата игра «Жизнь» на диагональных координатных решетках.
Ключевые слова: клеточный автомат, игра «Жизнь», диагональная решетка
Математическое и компьютерное моделирование лежит в основе множества удивительных технических достижений последнего времени. Особую роль в компьютерном моделировании различных процессов из физики, экономики, биологии, социологии, вообще, в любой науке, которая изучает эволюционирующие системы, играет теория так называемых клеточных автоматов — комбинаторных объектов, которые удивительно хорошо описывают явления из этих областей и позволяют получать весьма точные прогнозы.
В 1970 году английский математик Джон Конвей придумал игру под названием «Жизнь» (см. [1], [2], [3], [5]), являющуюся частным случаем клеточного автомата. Очень скоро эта игра приобрела невероятную популярность среди специалистов по компьютерному моделированию и, шире, теоретической информатике и кибернетике. Причина этому заключается в том, что при очень простых правилах эта игра позволяет конструировать очень сложные структуры и модели. Более того, оказывается, что весьма простые исходные данные иногда продуцируют совершенно нетривиально эволюционирующие системы.
Наша работа посвящена изучению поведения так называемых решёток — бесконечных колоний, строгое определение которых даётся в Главе 2; сказанное выше говорит о несомненной актуальности выбранной темы. Более подробно, перед нами стояли следующие цели и задачи:
Изучить правила игры «Жизнь», проследить эволюцию нескольких поколений различных простейших колоний.
Дать строгое определение решёток, изучить поведение нескольких видов решёток с небольшим шагом.
Проанализировать эволюцию некоторых решёток с шагом n для произвольного натурального n.
Гипотеза об эволюции диагональных решёток. Выдвинем научное предположение об эволюции диагональных решёток со стороной равной n. Проанализировав колонии со сторонами 3–10, мы заметили такую закономерность, что решётка с чётным шагом будет вечной периодической (период равен двум), а решётка с нечётным шагом является вечной стабильной. На основании данных наблюдений можно сформулировать гипотезу для произвольного n (n-целое число). Если сторона решётки n делится без остатка на два, то через некоторое число ходов её конечная конфигурация станет вечной периодической (период равен двум). Если сторона решётки n делится на два с остатком один, то бактерии на доске в конечном итоге образуют вечную стабильную конфигурацию.
Теорема об эволюции координатных решёток. Докажем теорему об эволюции координатных решёток со стороной равной n (n-целое число). Рассмотрим несколько случаев:
а) сторона равная n делится без остатка на два. То есть n- целое чётное число. Ранее мы рассмотрели эволюцию решётки с n равной 8, 10, 12 и 14. Проведя анализ, можно заметить следующее, что эволюция каждой решётки со стороной n сводится через несколько ходов к одним и тем же конфигурациям. На рисунке 1 показаны конфигурации, которые получаются в результате эволюции решётки, где n-чётное число. И из этого можно заметить, что конфигурации получаются вечные стабильные, так как при первом ходе такой решётки рождается конфигурация, которая сразу же становится вечной стабильной.
Если при эволюции координатных решёток со стороной n, n число, делящееся на два, и последние три хода выглядят так, как показаны на рисунке 1, то в конечном итоге получится вечная стабильная колония.
Рис. 1.
Рис. 2.
Рис. 3.
Рис. 4.
б) сторона равная n делится на четыре с остатком 1. Ранее мы рассмотрели эволюцию решёток с n равной 9, 13. Проведя анализ, можно заметить, что через некоторое число ходов с таким значением n в конечном итоге получится колония, которая показана на рисунке 1, и она будет вечной стабильной, как и в предыдущем случае.
Если при эволюции координатных решёток со стороной n, n число, которое делится на четыре с остатком один и получится колония с рисунка 1, то в результате будет вечная стабильная колония.
Рис. 5.
в) сторона равная n делится на четыре с остатком 3. Ранее мы рассмотрели эволюцию решёток со стороной n равной 11 и 15. Проведя анализ можно заметить следующее, что через некоторое число ходов с таким значением n в конечном итоге получится колония, которая показана на рисунке 1, и она в конечном итоге будет вечной периодической.
Рис. 6.
Если при эволюции координатных решёток со стороной n, n число, которое делится на четыре с остатком три и получится колония с рисунка 1, то в результате сформируется вечная периодическая колония.
Заключение
Итак, мы решили все поставленные во введении задачи; проанализировали поведение простейших решёток, сформулировали гипотезу об эволюции диагональных решёток для произвольного n и доказали теорему об эволюции координатных решёток для произвольного n. Опишем кратко возможные обобщения наших результатов.
Конечно, в первую очередь хотелось бы доказать сформулированную нами гипотезу о поведении диагональных решёток для произвольного n; сейчас мы работаем над этим доказательством.
Далее, хочется распространить наши результаты на случай произвольных решёток с любой длиной стороны «параллелограмма», образованного пересекающимися прямыми и с любыми углами прямых. Эта общая задача имеет прямое отношение к моделированию поведения сложных систем в химии и в генетике, см., к примеру, [1].
Относительно недавно (в начале XX века) в ряде работ возникла так называемая квантовая версия игры жизнь, когда в каждой клетке поля написано число от 0 до 1, трактуемое как вероятность нахождения бактерии на этом поле. Таким образом, на каждом шаге вычисляется вероятность того, что в этой точке находится бактерия. Интересным представляется проанализировать эволюцию решёток в такой постановке. (Впрочем, для квантовой версии пока получены только самые первые результаты, так что эта задача может быть гораздо более сложной, чем классическая.)
Литература:
- Adamatzky A. Game of life cellular automata. Springer, 2010..
- Gardner M. The fantastic combinations of John Conway's new solitaire game «life». // Scientific American 223 (1970), 120–123.
- Weisstein E. Treasure trove. The life cellular automaton, available at http://www.ericweisstein.com/encyclopedias/life.
- Виленкин Н. Я. Виленкин А. Н., Виленкин П. А. Комбинаторика. — М.: МЦНМО, 2007.
- Гарднер М. Математические досуги. — М.: Мир, 1972.
- Клумова Н. Н. Игра «Жизнь». // Квант, 1974, № 9, с. 26–30.
