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