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

Материал из Википедии — свободной энциклопедии

Муравей Лэнгтона — это двумерная машина Тьюринга с очень простыми правилами, изобретенная Крисом Лэнгтоном.

Рассмотрим бесконечную плоскость, разбитую на клетки, покрашенные некоторым образом в черный и белый цвет. Пусть в одной из клеток находится «муравей», который на каждом шаге может двигаться в одном из четырёх направлений в клетку, соседнюю по стороне. Муравей движется согласно следующим правилам:

• На черном квадрате — повернуть на 90° вправо, изменить цвет квадрата на противоположный, сделать шаг вперед на следующую клетку
• На белом квадрате — повернуть на 90° влево, изменить цвет квадрата на противоположный, сделать шаг вперед на следующую клетку

Эти простые правила вызывают довольно сложное поведение: после некоторого периода довольно случайного движения, муравей, видимо, начинает непременно строить дорогу из 104 шагов, повторяющуюся бесконечно, независимо от изначальной раскраски поля. Это наводит на мысль, что «магистральное» поведение является аттрактором муравья Лэнгтона.

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

3 муравья Лэнгтона с различными цветами:

[править] Обобщения муравья Лэнгтона

Существует простое обобщение муравья Лэнгтона, в котором используется более двух цветов клеток. Цвета изменяются циклически. Для таких муравьев существует также простая форма названия: для каждого следующего цвета используется буква 'L' или 'R' ('Л' и 'П'), в зависимости от того, поворачивает ли муравей направо или налево. Таким образом, муравей Лэнгтона — это муравей 'RL'.

Некоторые из этих обобщенных муравьев Лэнгтона рисуют узоры, которые становятся все более симметричными. Один из простых примеров — муравей 'RLLR'. Одно достаточное условие этого заключается в том, что имя муравья, рассматриваемое как циклический список, состоит из последовательных пар повторяющихся букв 'LL' или 'RR' (цикличность списка означает, что последняя буква может спариваться с первой).

Смотрите также:

• Черви Петерсона

[править] Ссылки

• Further Travels with my Ant, D. Gale, J. Propp, S. Sutherland, и S. Troubetzkoy: статья в форматах PostScript или TeX, содержащая доказательство указанного выше достаточного условия симметричности узора.
• http://www.theory.org/software/ant/
• http://www.math.sunysb.edu/~scott/ants/
• http://www.hut.fi/~jblomqvi/langton/index.html многоцветный Java апплет с программируемыми муравьями.
• http://yoda.neostrada.pl/ ASM32 приложение с возможностями увеличения, добавления препятствий, сохранения/загрузки, обращения цветов, пошаговым режимом
• http://www.fortunecity.com/emachines/e11/86/langton.html Колонка Математических Развлечений в Scientific American, использующая муравья Лэнгтона как метафору для Теории Великого Объединения
• http://www.ing-mat.udec.cl/~anahi/langton Java апплет с несколькими полями и редактируемыми рисунками, показывает, как муравей может рассчитывать логические схемы.