Пример 1

Алфавит состоит из цифр 0,1,…,9. На ленте написано слово:

…

2

0

9

3

1

…

и головка показывает на 9. Тогда в следующий такт времени головка может записать вместо 9 цифру 8 и переместиться влево. После этого она будет показывать на 0.

Перейдем к точным определениям.

Машиной Тьюринга T  =  (A,Q,) называется тройка, состояний из непустых конечных множеств A  =  {a₀,a₁,…,a_n}, Q  =  {q₀,q₁,…,q_m} и частичной функции :  Q  A  Q  A  {L,S,R}.

Здесь {L,S,R} – множество, состоящее из трех элементов. Оно одинаково для всех машин Тьюринга и интерпретируется командами перемещения головки: L – влево, R – вправо, S – стоять на месте.

Множество А называется внешним алфавитом, его элементы – буквами. Буквы a₀ и a₁ для всех машин Тьюринга одинаковы: a₀ = 0, a₁ = 1. Элементы q₀,…,q_m называются внутренними состояниями.

Частичная функция  называется программой и записывается или с помощью прямоугольной таблицы, в которой в клетке (q_i,q_j) записывается тройка (q_i,q_j)    Q  A  {L, S, R}, или с помощью списка команд вида:

• q_ia_j  q_ka_e означающей (q_k,a_e,S) = (q_i,a_j),

• q_ia_j  q_ka_eR означающей (q_k,a_e,R) = (q_i,a_j),

• q_ia_j  q_ka_eL означающей (q_k,a_e,L) = (q_i,a_j).

Эти команды обозначим через T(i,j).

Машиным словом, или конфигурацией, называется слово вида: q_ka_e, где 0    k    m, 0    e    n,  и  – слова (возможно, пустые), составленные из букв алфавита А. Для обозначения слова аа…а, в котором буква а повторяется x раз, пишем: а^х.

Машинное слово: q_ka_e интерпретируется как положение, при котором головка указывает на символ a_e, машина находится во внутреннем состоянии q_k, слева от текущей ячейки находятся символы, составляющие слово , а справа – слово . В примере 1 машинное слово равно: 20q_i931 для некоторого i.

Пусть задана машина Тьюринга Т и машинное слово M  =  q_ia_j, где 0    i   m. Обозначим через M_T’ слово, которое получается (за один такт) по правилам:

1) для i  =  0 положим M_T’ = M;

2) для i  >  0 выполняем одно из следующих трех преобразований:

• если T(i,j)  =  q_ia_j  q_ka_e, то M_T’ =  q_ka_e;

• в случае T(i,j)  =  q_ia_j q_ka_eR,

если  не пусто, то M_T’ =  q_ea_k, иначе MT ’=  q_ea_ka₀;

• в случае T(i,j)  =  q_ia_j  q_ka_eL,

если  = ₁a_s для некоторых ₁ и a_s, то MT’ =  ₁q_ka_sa_e,

иначе (т.е. если  пусто) MT’= q_ka₀a_e (дополнительная инструкция).

Положим: M_T⁰ =  M, M_T⁽ⁿ⁺¹⁾ =  (M_T⁽ⁿ⁾)’.

Будем говорить, что машина Т перерабатывает машинное слово М в слово М₁, если M_T⁽ⁿ⁾  =  M₁ для некоторого n    0. Пишем: М  _T M₁, если Т перерабатывает М в М₁, и при этом не используется дополнительная инструкция (из правил образования слова M_T’).

Говорим, что машина Т вычисляет частичную функцию f: Nⁿ  N, если выполнены следующие условия:

• если (x₁,…,x_n)  Dom(f), то машина Т останавливается, т.е. перерабатывает слово q₁01^x10…1^xn0 в некоторое слово q₀, и при этом q₀ содержит f(x₁,…,x_n) вхождений символа 1 (здесь символы x₁, … , x_n обозначены через x1, ..., xn) ;

• если (x₁,…,x_n) не принадлежит Dom(f), то машина, начиная со слова M  = q₁01^x10…1^xn0, работает бесконечно, т.е. q₀ не входит в M_T⁽ⁿ⁾ ни для каких n    0.

Говорим, что машина Т правильно вычисляет частичную функцию f: Nⁿ  N, если выполнены условия:

• если (x₁,…,x_n)  Dom(f), то q₁01^x10…1^xn0 _Tq₀01^f(x1,…,xn)0…0;

• в противном случае машина, начиная со слова q₁01^x10…1^xn0, работает бесконечно.

Частичная функция f называется (правильно) вычислимой, если существует машина Тьюринга, которая (правильно) вычисляет f.