Тьюрмиты (M,Zjbnmd)

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

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

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

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

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

Примеры

• 
• 
• 
• 
• 
• 

См. также

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