7.2. Машины Тьюринга

Рассмотрим гипотетическую «машину», имеющую конечное множество Q внутренних состояний и одну бесконечную ленту, разделенную на ячейки, по которой перемещается устройство для чтения и записи, именуемое головкой. В каждый из такт времени головка читает содержимое текущей ячейки, затем пишет в эту ячейку новый символ и перемещается влево или вправо, или остается на месте. Текущей ячейкой становится новая ячейка, она будет той, на которую указывает головка. Символы принадлежат конечному алфавиту А.