Тюрміти

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

Тюрміти за своєю обчислювальною здатністю еквівалентні звичайній одновимірній машині Тюрінга.

Тюрміти з відносною і абсолютною орієнтацією

Тюрміти можна розділити на тюрміти з відносною і абсолютною орієнтацією. Тюрміти з відносною орієнтацією мають внутрішню орієнтацію. Команди в програмі містять зміни орієнтації відносно поточної: «ліворуч», «вперед», «праворуч», «розвернутися». Прикладом такого тюрміту є мураха Ленгтона.

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