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

Тьюрмиты по своей вычислительной способности эквивалентны обычной одномерной машине Тьюринга .

Тьюрмиты с относительной и абсолютной ориентацией

Тьюрмиты можно разделить на тьюрмиты с относительной и абсолютной ориентацией. Тьюрмиты с относительной ориентацией имеют внутреннюю ориентацию. Команды в программе содержат изменение ориентации относительно текущей: «налево», «вперёд», «направо», «развернуться». Примером такого тьюрмита является муравей Лэнгтона .

Тьюрмиты с абсолютной ориентацией, иногда называемые просто «двумерные машины Тьюринга », используют в программах абсолютное смещение («на север», и.т.д.)

Примеры

См. также

• Муравей Лэнгтона
• Машина Тьюринга