турмит
В информатике турмит , — это машина Тьюринга имеющая помимо текущего состояния ориентацию и «ленту», состоящую из бесконечной двумерной сетки ячеек. термины муравей и вант Также используются . Муравей Лэнгтона — известный вид турмитов, определяемый по ячейкам квадратной сетки. Черви Патерсона — это разновидность турмита, определяемая по краям изометрической сетки .
Было показано, что турмиты в целом по мощности точно эквивалентны одномерным машинам Тьюринга с бесконечной лентой, поскольку одна из них может имитировать другую.
История
[ редактировать ]Муравьи Лэнгтона были изобретены в 1986 году и объявлены «эквивалентными машинам Тьюринга». [1] Независимо, в 1988 году Аллен Х. Брэди рассмотрел идею двумерных машин Тьюринга с ориентацией и назвал их «машинами Тьюринга». [2] [3]
Очевидно, независимо от того и другого, [4] Грег Терк исследовал такую же систему и написал о ней А. К. Дьюдни . А. К. Дьюдни назвал их «тур-клещами» в своей колонке «Компьютерные развлечения» в журнале Scientific American в 1989 году. [5] Руди Ракер рассказывает эту историю следующим образом:
Дьюдни сообщает, что, подыскивая название для существ Тёрка, он подумал: «Ну, это машины Тьюринга, изученные Тёрком, так что они должны быть чем-то турнским. И они похожи на маленьких насекомых или клещей, так что я» Я назову их турклещами! А это похоже на термитов!» С любезного разрешения Тёрка и Дьюдни я опущу дефис и назову их турмитами.
— Руди Ракер, Лаборатория искусственной жизни [4]
Относительные и абсолютные турмиты
[ редактировать ]Турмитов можно разделить на относительные и абсолютные . Относительные турмиты, также известные как «токарные станки», имеют внутреннюю ориентацию. Муравей Лэнгтона является таким примером. Относительные турмиты по определению изотропны ; вращение турмита не влияет на его исход. Относительные турмиты названы так потому, что направления закодированы относительно текущей ориентации, что эквивалентно использованию слов «влево» или «назад». Для сравнения, абсолютные турмиты кодируют свои направления в абсолютных терминах: определенная инструкция может приказать турмиту двигаться «на север». Абсолютные турмиты являются двумерными аналогами обычных машин Тьюринга, поэтому их иногда называют просто «двумерными машинами Тьюринга». Оставшаяся часть этой статьи посвящена относительному случаю.
Спецификация
[ редактировать ]Следующая спецификация относится только к турмитам на двумерной квадратной сетке, наиболее изученному типу турмитов. Турмиты на других сетках можно указать аналогичным образом.
Как и в случае с муравьем Лэнгтона, турмиты каждый такт выполняют следующие операции:
- развернуться на месте (на угол, кратный 90°)
- изменить цвет квадрата
- продвиньтесь вперед на одну клетку.
Как и в случае с машинами Тьюринга, действия определяются таблицей переходов состояний , в которой указано текущее внутреннее состояние турмита и цвет ячейки, в которой он в данный момент находится. Например, турмит, показанный на изображении вверху этой страницы, определяется следующей таблицей:
| Текущий цвет | |||||||
|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||
| Написать цвет | Повернуть | Следующее состояние | Написать цвет | Повернуть | Следующее состояние | ||
| Текущее состояние | 0 | 1 | Р | 0 | 1 | Р | 1 |
| 1 | 0 | Н | 0 | 0 | Н | 1 | |
Направление поворота — одно из следующих: L (90° влево), R (90° вправо), N (без поворота) и U ( разворот на 180° ).
Примеры
[ редактировать ]- Примеры двухцветных турмитов с двумя состояниями на квадратной сетке , все начиная с пустой конфигурации:
Спиральный рост.
Производство шоссе после периода хаотического роста.
Хаотичный рост с характерной текстурой.
Рост с характерной текстурой внутри расширяющейся рамки.
Построение спирали Фибоначчи .
Создание растущего алмаза
- Примеры турмитов с большим количеством состояний и цветов и на неквадратных сетках:
Двухцветный турмит с тремя состояниями, образующий фрактальный узор в виде снежинок.
Трехцветный турмит с тремя состояниями на гексагональной сетке , хаотично растущий с характерной текстурой, прежде чем застревать в периодической петле примерно через 194150 шагов.
Начиная с пустой сетки или других конфигураций, наиболее часто наблюдаемым поведением является хаотический рост, спиральный рост и строительство «шоссе». Редкие примеры становятся периодическими после определенного количества шагов.
Игра Занятой бобер
[ редактировать ]Аллен Х. Брэйди искал уничтожающих турмитов (эквивалент занятых бобров ) и нашел двухцветную машину с двумя состояниями, которая печатала 37 единиц перед остановкой, а также другую, которая делала 121 шаг перед остановкой. [3] Он также рассмотрел турмитов, которые движутся по треугольной сетке , и нашел здесь также несколько занятых бобров.
Эд Пегг-младший рассмотрел другой подход к занятой бобровой игре. Он предположил, что турмиты могут поворачиваться, например , влево и вправо, разделяясь на две части. Турмиты, которые позже встречаются, уничтожают друг друга. В этой системе Занятой Бобер — это тот, который из стартового набора из одного турмита продержится дольше всех, прежде чем все турмиты уничтожат друг друга. [6]
Другие сетки
[ редактировать ]После первой работы Аллена Х. Брэди о турмитах на треугольной сетке шестиугольные плитки были также исследованы . Большая часть этой работы принадлежит Тиму Хаттону, и его результаты находятся в хранилище таблиц правил. Он также рассматривал турмитов в трех измерениях и собрал некоторые предварительные результаты. Аллен Х. Брэди и Тим Хаттон также исследовали одномерные относительные турмиты на целочисленной решетке , которые Брейди назвал ластами . (Одномерные абсолютные турмиты, конечно, известны просто как машины Тьюринга.)
См. также
[ редактировать ]- Клеточный автомат - дискретная модель, изучаемая в информатике.
- Муравей Лэнгтона - двумерная машина Тьюринга с эмерджентным поведением
- Черви Патерсона - семейство клеточных автоматов для моделирования пищевого поведения.
Ссылки
[ редактировать ]- ^ Лэнгтон, Крис Г. (1986). «Изучение искусственной жизни с помощью клеточных автоматов» (PDF) . Физика D: Нелинейные явления . 22 (1–3): 120–149. Бибкод : 1986PhyD...22..120L . дои : 10.1016/0167-2789(86)90237-X . hdl : 2027.42/26022 .
- ^ Брэди, Аллен Х. (1988). «Игра занятого бобра и смысл жизни». В Рольфе Херкене (ред.). Универсальная машина Тьюринга: обзор полувека . Спрингер-Верлаг. ISBN 0-19-853741-7 .
- ^ Jump up to: Перейти обратно: а б Брэди, Аллен Х. (1995). «Игра занятого бобра и смысл жизни» . В Рольфе Херкене (ред.). Универсальная машина Тьюринга: обзор полувека (2-е изд.). Спрингер-Верлаг. стр. 237–254. ISBN 3-211-82637-8 .
- ^ Jump up to: Перейти обратно: а б Ракер, Руди. «Лаборатория искусственной жизни» . Проверено 16 октября 2009 г.
- ^ Дьюдни, АК (сентябрь 1989 г.). «Компьютерные развлечения: двумерные машины Тьюринга и турмиты оставляют следы на плоскости». Научный американец . 261 : 180–183. doi : 10.1038/scientificamerican0989-180 .
- ^ Пегг-младший, Эд. «Математическая головоломка» . Проверено 15 октября 2009 г.
Внешние ссылки
[ редактировать ]
- «Веб-страница, демонстрирующая несколько турмитов» . Архивировано из оригинала 21 декабря 2013 г.
- Пегг-младший, Эд (7 июня 2004 г.). «Математические игры: 2D-машины Тьюринга» . МАА Онлайн. Архивировано из оригинала 16 мая 2013 г.
- Пегг-младший, Эд (27 октября 2003 г.). «Математические игры: возвращение к червям Патерсона» . МАА Онлайн. Архивировано из оригинала 23 марта 2004 г.
- Турмит , в MathWorld .
- Golly скрипт для генерации произвольных турмитов
- Турмиты и занятые бобры с абсолютным и относительным движением на квадратных, кубических, треугольных и шестиугольных сетках