Турмиты

Двумерные машины Тьюринга, рисующие спирали, ходы и кружевные узоры.

  • Turmite
Tile colors01
100%

Tap to drop a turmite, drag to paint tiles in its path; Rerun starts again from step 0 with the turmites and tiles you added. A turmite is a 2D Turing machine; its state table grows spirals, worms and lattices from one head.

Setup
1
130 × 130 cells
View
60 steps per second
280°

Как вам Турмиты?

О генераторе Турмиты

Популяризация
A. K. Dewdney, Scientific American, сентябрь 1989
Машина
Движущаяся головка с внутренним состоянием и таблицей правил
Пресеты
Highway, Spiral, Worm, Lattice
Турмиты
От 1 до 12 одновременно, до 300 шагов за кадр
Экспорт
PNG

Турмит — это двумерная машина Тьюринга: головка, которая перемещается по сетке цветных ячеек и хранит небольшое внутреннее состояние. На каждом шаге она считывает цвет под собой, сверяется с таблицей состояний, записывает новый цвет, поворачивает, сдвигается на одну ячейку вперёд и переходит в новое состояние. Муравей Лэнгтона — простейший турмит с одним состоянием, тогда как турмиты с несколькими состояниями способны рисовать гораздо более сложные узоры. В сентябре 1989 года A. K. Dewdney популяризировал их на страницах Scientific American.

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

Этот симулятор позволяет запускать от 1 до 12 турмитов со скоростью до 300 шагов за кадр. Выберите готовый пресет — Highway, Spiral, Worm или Lattice, добавляйте новых турмитов щелчком мыши, рисуйте препятствия на их пути, настраивайте размер сетки и оттенок, а затем экспортируйте результат в PNG.

Как пользоваться Турмиты

  1. Выберите машину. Выберите пресет Highway, Spiral, Worm или Lattice.
  2. Запустите процесс. Нажмите Play и увеличьте Steps per frame до 300, чтобы ускорить рост узора.
  3. Добавьте турмитов. Укажите число в Turmites (от 1 до 12) или кликайте по сетке: они используют одно поле и взаимодействуют друг с другом.
  4. Создайте помехи. Рисуйте курсором на пути турмита, чтобы наблюдать за изменением его траектории.
  5. Экспортируйте. Настройте параметры Grid и Hue, поставьте симуляцию на паузу и экспортируйте PNG.

Часто задаваемые вопросы

Что такое турмит?

Это машина Тьюринга, действующая на двумерной сетке. У неё есть внутреннее состояние и таблица правил: для каждой комбинации состояния и цвета клетки таблица указывает новый цвет, направление поворота и следующее состояние.

Чем турмит отличается от Муравей Лэнгтона?

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

Почему группа турмитов ведёт себя иначе, чем один?

Они считывают и перезаписывают клетки одного и того же поля. Их траектории пересекаются, нарушая исходные цепочки: турмит, который в одиночку строил аккуратную спираль, при столкновении может переключиться на совершенно другой узор.

Обладают ли турмиты полнотой по Тьюрингу?

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

Научные источники

  1. Dewdney, A. K. (1989). Computer Recreations: Two-dimensional Turing machines and tur-mites make tracks on a plane. Scientific American 261(3), 180–183.