Формальное определение машины Тьюринга.

Машина Тьюринга Т=<A,Q,> полностью определяется:

1. внешним алфавитом А=а₀, а_1… а_m;

2. Алфавитом внутренних состояний Q=q₀, q_1… q_n;

3. Программой, то есть совокупностью выражений Т(i, j) (i=0,n; j=0,m), каждое из которых имеет вид следующей команды q_j a_i  q_k a_L d_t (k=0,n; L=0,m; d_t  d_Л, d_п, d_н.

Машина Тьюринга есть формальная детерминированная система F.S=<L,D>=<A,S;A_x,R>, порождающая множествоLсвоих конфигураций (машинных слов)₁q_ja_i₂(₁,₂А^*,₁и₂ могут быть пустыми). Единственная аксиома – начальная конфигурацияq₀(А^*), правила выводаR– система команд (программа)Т(i,j).

Примечания:

1. Очевидно, что всякий алгоритм является формальной системой F.S, что следует из тезиса Тьюринга: «Любой алгоритм может быть реализован машиной Тьюринга».

2. Поскольку машина Тьюринга есть алгоритм, то записью последнего является программа , а алгоритмом выполнения – описание устройства машины Тьюринга.

Пример:

Построить машину Тьюринга для вычисления базисной рекурсивной функции f(x)=x+1, xN₀ Имеем T=<A=a₀, Q=q₀, q_z, =

>

или

Пусть:

а) х=0, тогда q₀ a₀…a₀ q_zd_н;

б) х=2, тогда q₀ a₀ q₀ d_n q₀ a₀ d_n q_z d_н