Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Команды перемещений ленты

• L («Left») на ячейку влево,
• R («Right») на ячейку вправо
• S («Stop») остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным.

Элементарный шаг (такт) работы машины Тьюринга

• головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние

Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и положение головки

• Определение Конфигурация машины- совокупность состояний всех ячеек ленты, состояния УУ и положение головки
• В зависимости от начальной конфигурации возможны два варианта :
• после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;
• остановки не происходит.
• В первом случае говорят, что данная машина применима к начальной информации, во втором – нет.