Category:

Муравей Лэнгтона

Муравей Лэнгтона- пример клеточного автомата, придуманный Крисом Лэнгтоном.
По бесконечной плоскости, состоящей из белых и чёрных клеток, движется одинокий муравей с двумя банками краски. Правила поведения муравья:
1) Если клетка белая, муравей перекрашивает её в чёрный цвет, поворачивает на 90 градусов вправо и делает шаг вперёд.
2) Если клетка чёрная- перекрашивает в белый, поворачивет на 90 градусов влево, делает шаг вперёд.
Очень скоро движения муравья превращаются в настоящий хаос. Он может делать десятки тысяч шагов без каких-либо видимых глобальных закономерностей. Но каким бы ни было изначальное поле, в какой-то момент муравей обязательно начинает строить "магистраль" из 104 шагов:
Математикам пока не удалось доказать, что муравей строит свою магистраль всегда.
Вопрос: имеется ли здесь новая закономерность, неизвестная науке?