Эволюция клеточного автомата (игра «Жизнь») на диагональных решетках | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 8 октября, печатный экземпляр отправим 12 октября.

Опубликовать статью в журнале

Автор:

Рубрика: Математика

Опубликовано в Молодой учёный №3 (345) январь 2021 г.

Дата публикации: 12.01.2021

Статья просмотрена: 36 раз

Библиографическое описание:

Солдусова, Е. О. Эволюция клеточного автомата (игра «Жизнь») на диагональных решетках / Е. О. Солдусова. — Текст : непосредственный // Молодой ученый. — 2021. — № 3 (345). — С. 3-8. — URL: https://moluch.ru/archive/345/77519/ (дата обращения: 29.09.2022).



В статье автор исследует эволюцию клеточного автомата игра «Жизнь» на диагональных координатных решетках.

Ключевые слова: клеточный автомат, игра «Жизнь», диагональная решетка

Математическое и компьютерное моделирование лежит в основе множества удивительных технических достижений последнего времени. Особую роль в компьютерном моделировании различных процессов из физики, экономики, биологии, социологии, вообще, в любой науке, которая изучает эволюционирующие системы, играет теория так называемых клеточных автоматов — комбинаторных объектов, которые удивительно хорошо описывают явления из этих областей и позволяют получать весьма точные прогнозы.

В 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, трактуемое как вероятность нахождения бактерии на этом поле. Таким образом, на каждом шаге вычисляется вероятность того, что в этой точке находится бактерия. Интересным представляется проанализировать эволюцию решёток в такой постановке. (Впрочем, для квантовой версии пока получены только самые первые результаты, так что эта задача может быть гораздо более сложной, чем классическая.)

Литература:

  1. Adamatzky A. Game of life cellular automata. Springer, 2010..
  2. Gardner M. The fantastic combinations of John Conway's new solitaire game «life». // Scientific American 223 (1970), 120–123.
  3. Weisstein E. Treasure trove. The life cellular automaton, available at http://www.ericweisstein.com/encyclopedias/life.
  4. Виленкин Н. Я. Виленкин А. Н., Виленкин П. А. Комбинаторика. — М.: МЦНМО, 2007.
  5. Гарднер М. Математические досуги. — М.: Мир, 1972.
  6. Клумова Н. Н. Игра «Жизнь». // Квант, 1974, № 9, с. 26–30.
Основные термины (генерируются автоматически): конечный итог, сторона, эволюция, клеточный автомат, компьютерное моделирование, число ходов, n-целое число, вечная стабильная колония, игра, колония.


Ключевые слова

клеточный автомат, игра «Жизнь», диагональная решетка

Похожие статьи

Таксономия образовательных целей Бенджамина Блума

Его классификация образовательных целей, «Таксономия образовательных целей. Руководство 1: Когнитивная область» опубликованная в 1956 году, рассматривает когнитивную область в сравнении с психомоторной и аффективной областями знаний.

Использование клеточных автоматов для моделирования...

Клеточные автоматы – математические объекты с дискретными пространством и временем.

Модели клеточных автоматов используются в экологии и при моделировании эволюции.

При этом обычно для одного и того же набора правил существует конечный набор более или...

Теория игр: основные понятия, типы игр, примеры

Элементами игры являются ходы. Ход — это момент игры

Игра называется конечной, если каждый игрок имеет конечное число возможных стратегий, и бесконечной — в противном случае.

Из двух типов игр, кооперативные описывают процесс игры в целом, в то время как...

Совладающее поведение: аналитический обзор зарубежных...

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

Анализ концепций изучения города представителями Чикагской...

В статье рассматриваются концепции исследования города представителями Чикагской школы социологии: концепция экологического подхода Р. Парка и концепция описания города как образа жизни Л. Вирта.

Как появилось число нуль? | Статья в журнале «Юный ученый»

Он лишь показывал, появившись, например, внутри числа "101", что в этом числе нет ни одной "двадцатки". Лишь у индийцев впервые в истории человечества появляется ноль как математический символ, используемый в счетных операциях.

Реализация квантовых вычислений в программе Excel

В статье кратко изложены основы теории квантовых вычислений. Рассматриваются свойства кубитов, правила преобразования над ними, различные типы квантовых гейтов. Описан пример реализации квантового алгоритма Гровера в программе EXCEL. Показано преимущество...

Теория игр в экономике и международных отношениях

Теория игр определяет значение стратегии чистого конфликта. На сегодняшний день теоретико-игровые исследования отношений на международном уровне

В статье описывается понятие и сущность теории игр, определяется значение данной теории в современном мире, приводятся...

Похожие статьи

Таксономия образовательных целей Бенджамина Блума

Его классификация образовательных целей, «Таксономия образовательных целей. Руководство 1: Когнитивная область» опубликованная в 1956 году, рассматривает когнитивную область в сравнении с психомоторной и аффективной областями знаний.

Использование клеточных автоматов для моделирования...

Клеточные автоматы – математические объекты с дискретными пространством и временем.

Модели клеточных автоматов используются в экологии и при моделировании эволюции.

При этом обычно для одного и того же набора правил существует конечный набор более или...

Теория игр: основные понятия, типы игр, примеры

Элементами игры являются ходы. Ход — это момент игры

Игра называется конечной, если каждый игрок имеет конечное число возможных стратегий, и бесконечной — в противном случае.

Из двух типов игр, кооперативные описывают процесс игры в целом, в то время как...

Совладающее поведение: аналитический обзор зарубежных...

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

Анализ концепций изучения города представителями Чикагской...

В статье рассматриваются концепции исследования города представителями Чикагской школы социологии: концепция экологического подхода Р. Парка и концепция описания города как образа жизни Л. Вирта.

Как появилось число нуль? | Статья в журнале «Юный ученый»

Он лишь показывал, появившись, например, внутри числа "101", что в этом числе нет ни одной "двадцатки". Лишь у индийцев впервые в истории человечества появляется ноль как математический символ, используемый в счетных операциях.

Реализация квантовых вычислений в программе Excel

В статье кратко изложены основы теории квантовых вычислений. Рассматриваются свойства кубитов, правила преобразования над ними, различные типы квантовых гейтов. Описан пример реализации квантового алгоритма Гровера в программе EXCEL. Показано преимущество...

Теория игр в экономике и международных отношениях

Теория игр определяет значение стратегии чистого конфликта. На сегодняшний день теоретико-игровые исследования отношений на международном уровне

В статье описывается понятие и сущность теории игр, определяется значение данной теории в современном мире, приводятся...

Задать вопрос