Турмит - Turmite

Не путать с Термит.
Двухцветный турмит с двумя состояниями на квадратной сетке. Начиная с пустой сетки, после 8342 шагов турмит (красный пиксель) демонстрирует как хаотические, так и регулярные фазы движения.

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

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

История

Муравьи Лэнгтона были изобретены в 1986 году и объявлены «эквивалентными машинам Тьюринга».[1] Независимо в 1988 году Аллен Х. Брэди рассмотрел идею двухмерных машин Тьюринга с ориентацией и назвал их «токарными станками».[2][3]

Очевидно, независимо от того и другого,[4] Грег Терк исследовал такую ​​же систему и написал А. К. Дьюдни о них. А. К. Дьюдни назвал их «тур-митами» в своей колонке «Компьютерные развлечения» в Scientific American в 1989 г.[5] Руди Ракер рассказывает историю следующим образом:

Дьюдни сообщает, что, пытаясь найти имя для существ Турка, он подумал: «Ну, это машины Тьюринга, которые изучал Тюрк, так что они должны быть турками. И они похожи на маленьких насекомых или клещей, так что я» Назовем их тур-клещами! И это похоже на термитов! " С любезного разрешения Тёрка и Дьюдни, я собираюсь опустить дефис и называть их турмитами.

— Руди Ракер, Лаборатория искусственной жизни[4]

Относительные и абсолютные турмиты

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

Технические характеристики

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

Как и в случае с муравьем Лэнгтона, турмиты на каждом временном шаге выполняют следующие операции:

  1. повернуть на месте (кратно 90 °)
  2. изменить цвет квадрата
  3. продвинуться на один квадрат вперед.

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

Текущий цвет
01
Пишите цветПовернутьСледующее состояниеПишите цветПовернутьСледующее состояние
Текущее состояние01р01р1
10N00N1

Направление поворота - одно из L (90 ° влево), р (90 ° вправо), N (нет поворота) и U (180° Разворот ).

Примеры

  • Примеры двухуровневых двухцветных турмитов на квадратная сетка, все начинается с пустой конфигурации:

  • Спиральный рост.

  • Строительство шоссе после периода хаотичного роста.

  • Хаотичный рост с характерной текстурой.

  • Росток с характерной текстурой внутри расширяющейся рамки.

  • Строительство Спираль Фибоначчи.

  • Примеры турмитов с большим количеством состояний и цветов и на неквадратных решетках:

  • Трехуровневый двухцветный турмит, образующий снежинку. фрактал шаблон.

  • Трехцветный трехсторонний турмит на шестиугольная сетка, хаотически растущий с характерной текстурой, прежде чем застрять в периодической петле примерно после 194150 шагов.

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

Игра занятого бобра

Аллен Х. Брэди искал уничтожающие турмиты (эквивалент занятые бобры ) и обнаружил двухцветную машину с двумя состояниями, которая напечатала 37 единиц перед остановкой, и еще одну, которая сделала 121 шаг перед остановкой.[3] Он также считал турмиты, которые движутся по треугольная сетка, обнаружив здесь несколько занятых бобров.

Эд Пегг младший рассмотрел другой подход к занятой игре бобра. Он предложил турмиты, которые могут вращаться, например обе слева и справа, разделившись на две части. Турмиты, которые встречаются позже, уничтожают друг друга. В этой системе занятый бобер - это такой бобр, который из начального паттерна одного турмита длится дольше всех, прежде чем все турмиты уничтожат друг друга.[6]

Другие сетки

Следуя первоначальной работе Аллена Х. Брэди о турмитах на треугольной сетке, шестиугольные мозаики также были исследованы. Большая часть этой работы принадлежит Тиму Хаттону, и его результаты находятся в репозитории таблиц правил. Он также рассмотрел турмиты в трех измерениях и собрал некоторые предварительные результаты. Аллен Х. Брэди и Тим Хаттон также исследовали одномерные относительные турмиты на целочисленная решетка, который Брэди назвал ласты. (Одномерный абсолютный турмиты, конечно, просто известны как машины Тьюринга.)

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

Рекомендации

  1. ^ Лэнгтон, Крис Г. (1986). «Изучение искусственной жизни с помощью клеточных автоматов» (PDF). Physica D: нелинейные явления. 22 (1–3): 120–149. Bibcode:1986ФИД ... 22..120Л. Дои:10.1016 / 0167-2789 (86) 90237-Х. HDL:2027.42/26022.
  2. ^ Брэди, Аллен Х. (1988). «Оживленная игра бобра и смысл жизни». В Рольф Херкен (ред.). Универсальная машина Тьюринга: обзор за полвека. Springer-Verlag. ISBN  0-19-853741-7.
  3. ^ а б Брэди, Аллен Х. (1995). «Занятая бобровая игра и смысл жизни». В Рольф Херкен (ред.). Универсальная машина Тьюринга: обзор за полвека (2-е изд.). Springer-Verlag. С. 237–254. ISBN  3-211-82637-8.
  4. ^ а б Ракер, Руди. «Лаборатория искусственной жизни». Получено 16 октября, 2009.
  5. ^ Дьюдни, А. К. (сентябрь 1989 г.). «Компьютерные развлечения: двумерные машины Тьюринга и турмиты создают треки на плоскости». Scientific American. 261: 180–183. Дои:10.1038 / scientificamerican0989-180. закрытый доступ
  6. ^ Пегг-младший, изд. «Математическая головоломка». Получено 15 октября 2009.

внешняя ссылка