Александров, Виктор Борисович
- 1 year ago
- 0
- 0
В информатике Тьюрмит — это машина Тьюринга , которая имеет ориентацию в пространстве, текущее состояние и «ленту», состоящую из бесконечного двухмерного массива ячеек. Примерами тьюрмитов могут служить муравей Лэнгтона , определённый на ячейках квадратной сетки , и черви Патерсона , определённые на рёбрах треугольной сетки .
Тьюрмиты по своей вычислительной способности эквивалентны обычной одномерной машине Тьюринга .
Тьюрмиты можно разделить на тьюрмиты с относительной и абсолютной ориентацией. Тьюрмиты с относительной ориентацией имеют внутреннюю ориентацию. Команды в программе содержат изменение ориентации относительно текущей: «налево», «вперёд», «направо», «развернуться». Примером такого тьюрмита является муравей Лэнгтона .
Тьюрмиты с абсолютной ориентацией, иногда называемые просто «двумерные машины Тьюринга », используют в программах абсолютное смещение («на север», и.т.д.)