Машина Тьюринга как формальная модель алгоритма. Тезис Тьюринга

qn}.
Алфавит: Σ= {a1,…,am}.
Формальное определение: МТ=(Q,Σ,δ,q0,qz,a0,ar)
Команда МТ: qi aj

→q’i a’j S (S – направление сдвига :L – влево ,R - вправо, E-на месте)
Конфигурации: произвольная - α1 qi α2 , стандартная начальная q0α, стандартная заключительная qzα
Переходы: непосредственный K→K’.
Если для K1 и Kn существует последовательность конфигураций K1, K2, …, Kn, такая, что K1 → K2 → …→ Kn,
то обозначим переход K1 =>Kn.

Все нули заменить на 2.





0 ->2 R
1->1 R
2 ->2 L
1

->1 L

ε ->ε L

ε ->ε R

1 -> 1R

ε -> ε R

Машина, работающая бесконечно на цепочке из 1:

β2, то будем говорить, что машина Т перерабатывает слово α1

α2 в слово β1β2, и обозначать это T(α1α2) = β1β2.
Унарный код:
x единиц 1…1 = 1x , ε=0.
q0 1х1 * 1х2 * … * 1 хn⇒ qz 1y , когда f ( x 1 , … , xn ) = y, и работает бесконечно, начиная со стандартной начальной конфигурации, если f(x1,…,x n ) не определена.

Примеры:функций, вычислимых по Тьюрингу: сложение чисел , копирование.

- машины, вычисляющие f1 и f2 :
Q1

= {q10,…,q1n } и Q2 = {q20,…,q2n }
Граф машины Т: q20 = q1z . Начальное состояние Т - q10, заключительное – q2z.

Пусть f2(f1(x)) определена. Тогда Т1(1x) = 1f1(x) и
q101x => q1z1f1 (x).
Машина Т:
вместо q1z1f 1(x) она перейдет в q201f 1(x).
Машина Т2: q201f1 (x) => q2z1f2 (f1(x)).
Машина Т: q101x => q201f1 (x) => q2z1f 2(f 1(x)) и, следовательно, Т(1x) = 1f2 (f1 (x)).

предикат P(α), если T(α) = ω, где ω = Т,

когда Р(α) истинно, и ω = F, когда P(α) ложно.
df Говорят, что машина Т вычисляет Р(α) с восстановлением, если Т(α) = ωα.

Доказательство теоремы о вычислимости с восстановлением:
q0α => qn1 α* α => α *qn2 α => α * qn3 ω => qn4 ωα.

по Тьюрингу, то разветвление g1(α) и g2(α) по Р(α) также

вычислимо.
Доказательство. Пусть Т1 – машина с состояниями q10,q11,…,q1n и системой команд , вычисляющая g1, Т2 – машина с состояниями q20,q21,…, q2n и системой команд , вычисляющая g2; Тp вычисляет с восстановлением Р(α). Тогда машина Т, вычисляющая разветвление g1 и g2 по Р, - это композиция Тр и машины Т3, система команд которой имеет следующий вид: