Формально машина Тьюринга (Tm) - это
Q - конечное множество состояний;
D функция переходов, отображение из
Так определенная машина Тьюринга называется детерминированной. Недетерминированная машина Тьюринга для каждой пары
Шаг Tm определим следующим образом.
Пусть (q, A1, A2, ... An, i) - конфигурация Tm,
где
Если
(R от англ. Right), то
То есть Tm печатает символ A и передвигается вправо.
Если
(L от англ. Left), то если i = n, то допустимо A = B и
Tm печатает A и передвигается влево, но не за конец ленты.
Если i = n + 1, головка просматривает пустой символ B.
Если D(q, B) = (p, A, R), то
Если D(q, B) = (p, A, L), то допустимо A=B и
Если две конфигурации связаны отношением
Язык, допускаемый Tm, это множество таких слов из T*, которые будучи расположены в левом конце ленты переводят Tm из начального состояния q0 с начальным положением головки в самом левом конце ленты в конечное состояние. Формально, язык, допускаемй Tm, это
Если Tm распознает L, то Tm останавливается, то есть не имеет переходов после того, как слово допущено. Однако, если слово не допущено, возможно, что Tm не останавливается.
Язык, допускаемый некоторой Tm, называется рекурсивно перечислимым. Если Tm останавливается на всех входах, то говорят, что Tm задает алгоритм и язык называется рекурсивным.
Существует машина Тьюринга, которая по некоторому описанию произвольной Tm и кодированию слова x моделирует поведение Tm со входом x. Такая машина Тьюринга называется универсальной машиной Тьюринга.