Теория алгоритмов

Программой машины Тьюринга называется набор всех её команд. Работа машины Тьюринга связана с бесконечной лентой, разбитой на ячейки, причём в каждой ячейке может быть записан один символ некоторого алфавита, причём λ является символом пустой ячейки. Работа машины Тьюринга над словом α, записанным на ленте, проходит следующим образом: машина Тьюринга начинает свою работу всегда в состоянии s1, а её считывающее устройство расположено над первым слева символом слова, записанного на ленте; считав символ в ячейке, обозреваемой считывающим устройством машины Тьюринга, она печатает в эту ячейку символ, найденный с помощью функции выхода v, двигается вдоль ленты вправо, влево или остаётся на месте, в случае, если функция μ принимает значения П, Л или Н соответственно и переходит в состояние, определяемое с помощью функции перехода δ; при переходе машины Тьюринга в состояние s0 считают, что она закончила работу над словом а и говорят, что машина Тьюринга применима к слову α. Подробнее