Регистрация / Вход
Прислать материал

Эволюция клеточного автомата "муравей Лэнгтона" на торических решётках

Сведения об участнике
ФИО
Солдусова Елена Олеговна
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего образования «Самарский государственный технический университет»
Тезисы (информация о проекте)
Область наук
Математика. Механика
Раздел области наук
Математика
Тема
Эволюция клеточного автомата "муравей Лэнгтона" на торических решётках
Резюме
Дано определение торических решёток, изучено поведение муравья на нескольких видах решёток небольшого размера. Разработан и программно реализован в среде Pascal алгоритм, моделирующий поведение муравья Лэнгтона на произвольной торической решётке. С использованием данной программы посчитано количество шагов, через которые муравей «вернулся» в исходное положение, а торическая решётка «приобрела» белый цвет, также посчитано количество операций, по прошествии которых торическая решётка стала белой впервые. На основе этих данных сформулирована гипотеза и доказана теорема об эволюции клеточного автомата «муравей Лэнгтона» на торических решётках для произвольного n.
Ключевые слова
клеточные автоматы, комбинаторика, муравей Лэнгтона, торическая решётка
Цели и задачи
1. Изучить правила эволюции муравья Лэнгтона, проследить эволюцию нескольких поколений различных простейших начальных данных.
2. Дать определение торических решёток, изучить поведение муравья на нескольких видах решёток небольшого размера.
3. Проанализировать эволюцию некоторых решёток размера n для произвольного натурального n.
Введение

Относительно недавно большой интерес математиков и специалистов в компьютерных науках вызвал клеточный автомат, созданный Крисом Лэнгтоном, который чаще всего теперь называют «муравей Лэнгтона». Причина этому заключается в том, что при очень простых правилах этот автомат позволяет конструировать очень сложные структуры и модели. Более того, оказывается, что весьма простые исходные данные иногда продуцируют совершенно нетривиально эволюционирующие системы.

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

Методы и материалы

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

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

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

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

2.Затем хочется перенести эти результаты на случай прямоугольных торических решёток, которые получаются отождествлением противоположных сторон произвольного прямоугольника, а не обязательно квадрата.

3.Далее, хочется распространить наши результаты на случай цилиндрических решёток. Они описываются так же, как торические, с той лишь разницей, что у выбранного квадрата (или прямоугольника) отождествляется лишь одна пара противоположных сторон, а не обе.

4.Кроме того, интересно было бы исследовать поведение муравья Лэнгтона на торических или цилиндрических решётках с другими правилами, например, с большим количеством цветов. Отметим, что даже в классической постановке задаче в этом направлении пока получено очень мало результатов.

5.Наконец, вместо прямоугольных решёток можно брать треугольные или шестиугольне решётки (из которых, как известно, тоже можно склеить тор или более сложные двумерные поверхности) и анализировать поведение муравья на возникающих поверхностях.

Используемые источники
1. Виленкин Н.Я. Виленкин А.Н., Виленкин П.А. Комбинаторика. – М.: МЦНМО, 2007.
2. Гарднер М. Математические досуги. – М.: Мир, 1972.
3. O. Beuret, M. Tomassini. Behaviour of multiple generalized Langton’s ants. Artificial Life 5 (1997), 45-50.
4. J.P. Boon. How fast does Langton’a ant move? Preprint, see arXiv: cond-mat/0004331, 8 pp.
5. A. Gajardo, A. Moreira, E. Goles. Complexity of Langton’s ant. Discrete Applied Mathematics 117 (2002), no. 1-3, 41-50.
6. C.G. Langton. Studying artificial life with cellular automata, Physica D: Nonlinear Phenomena 22 (1986), no. 1-3, 120-149.
Information about the project
Surname Name
Soldusova Elena
Project title
Evolution of cellular automata "Langton's ant" on torus matrixes
Summary of the project
Conventions of interchange of Langton’s ant on infinite checked field were analyzed. Evolutions of several generations of various simplest initial-value particulars information were evaluated by means of these conventions. Examination of torus matrix was given; the study of behavior of solutions of ant on several-sorted matrixes of small size was analyzed. Simulating of the study of behavior of solutions of Langton’s ant on certain torus matrix algorithm was devised and implemented into software in Pascal. Number of steps wherethrough ant «returned» in the starting point but torus matrix «began» white was counted up using this programme. The hypothesis was formulated and the theorem was proved about evolution of cellular automata «Langton’s ant» on torus matrixes for arbitrary n by means of these particulars information.
Keywords
Cellular automata, combinatorics, Langton’s ant, torus matrix