Основные принципы работы вычислительной машины Тьюринга:

1. Преобразование входных данных с помощью последовательности элементарных действий. 1 Каждое действие меняет лишь одну ячейку, и возможные действия не могут быть бесконечными. 1
2. Устройство управления находится в определённом состоянии и способно перемещаться в обе стороны вдоль ленты. 3 Оно может записывать в ячейки и считывать из них алфавитные символы. 3
3. Управляющее устройство следует правилам перехода. 1 Каждое правило предписывает машине Тьюринга, в зависимости от текущего состояния и наблюдаемого в текущей ячейке символа, записать в эту ячейку новый символ, перейти в новое состояние и переместиться на одну ячейку вправо или влево. 1
4. Выбор действий основан на конечной таблице, которая определяет, что делать для каждой комбинации текущего состояния и считываемого символа. 4
5. Выполнение операций прекращается после того, как головка считывает пассивное состояние — q0. 5 Переход в любую подобную ячейку приводит к концу работы машины и остановки алгоритма. 1