В информатике Тьюрмит — это машина Тьюринга, которая имеет ориентацию в пространстве, текущее состояние и «ленту», состоящую из бесконечного двухмерного массива ячеек. Примерами тьюрмитов могут служить муравей Лэнгтона, определённый на ячейках квадратной сетки, и черви Патерсона, определённые на рёбрах треугольной сетки.
Тьюрмиты по своей вычислительной способности эквивалентны обычной одномерной машине Тьюринга.
Тьюрмиты с относительной и абсолютной ориентацией
Тьюрмиты можно разделить на тьюрмиты с относительной и абсолютной ориентацией. Тьюрмиты с относительной ориентацией имеют внутреннюю ориентацию. Команды в программе содержат изменение ориентации относительно текущей: «налево», «вперёд», «направо», «развернуться». Примером такого тьюрмита является муравей Лэнгтона.
Тьюрмиты с абсолютной ориентацией, иногда называемые просто «двумерные машины Тьюринга», используют в программах абсолютное смещение («на север», и.т.д.)
Примеры
См. также
Эта страница в последний раз была отредактирована 15 июля 2023 в 18:36.
Обычно почти сразу, изредка в течении часа.