WikiSort.ru - Не сортированное

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

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

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

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

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

Примеры

См. также

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

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