Неформальное определение
Устройство, состоящее из двух частей:
- бесконечной одномерной ленты, разделённой на ячейки,
- головки, которая представляет собой детерминированный конечный автомат.
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку. Если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
Формальное определение
вопрос найти формальное определение из лекций