Машина Тьюринга.

Машиной Тьюринга называется пятерка объектов: T=(A,S,,μ,), где А={a₁, a₂,..., a_n}- алфавит; λ – символ пустой ячейки. S={ s₀, s₁,..., s_m} – множество внутренних состояний, причем s₀ – заключительное, а s₁ – начальное состояния. Если при работе происходит переход в состояние s₀, то машина прекращает свою работу и говорят, что она применима для данного слова, т.е. зациклена.

ν: AS S – функция перехода;

μ: AS  A – функция выхода;

: AS  { Н,Л,П } – функция управления (на месте, лево, право).

Пример:

	s1	s2
λ	1, П, s2	1, Н, s0
1	1, П, s1	λ, П, s1

Считаем, что машина Т, при работе со словом, начинает работу из состояния s₁, а считывающее устройство зависает над первым слева непустым символом слова.

1 1 λ 1,	1 1 λ 1,	1 1 λ 1,	1 1 1 1,	1 1 1 λ λ,	1 1 1 λ 1
s1	s1	s2	s2	s2	s0

Таким образом Т(1²λ1)=1³λ1.

Конфигурацией машины Тьюринга в данный момент времени называется запись вида α₁, a_i, α₂, где α₁ – начало слова, a_i – символ в данный момент времени, α₂ – конец (хвост) слова.

Пример: Написать машину Тьюринга применимую к словам вида x₁, x₂,..., x_n (n≥2), где x_i{a,b}, и переводящую их в слово α=

	1	2	3	4	5
λ			λ Н 0	b П 5	b Н 0
a	a П 2	λ П 3	λ П 3	a П 4
b	b П 2	b П 4	λ П 3	b П 4

Проверим для слова abba:

a b b a	a b b a	a b b a	a b b a	a b b a λ	a b b a b λ	a b b a b b
1	2	4	4	4	5	0

Проверим для слова bab:

b a b	b a b	b λ b	b λ λ λ	b λ λ λ
1	2	3	3	0

Числовая функция

Числовая функция f(x₁, x₂,..., x_n) называется вычислимой по Тьюрингу, если существует машина Тьюринга, применимая к любому слову вида 1^x1+11^x2+1…1^xn+1, переводящая его в слово 1^y+1, где y= f(x₁, x₂,..., x_n).

Пример: доказать, что функция f(x,y)=x+y вычислима по Тьюрингу (т.е. 1^x+11^y+1  1^x+y+1).

	1	2	3	4
λ	1 П 2	λ Л 3
1	1 П 1	1 П 2	λ Л 4	λ Н 0

Пусть x₁=1, x₂=2. Покажем, что f(1,2)=3:

1 1λ111	1 1 λ111	11 λ 111	111 1 11	1111 1 1	11111 1 λ	111111 λ	11111 1 λ
1	1	1	2	2	2	2	3
1111 1 λλ	1111 λ λλ.
4	0

Мы получили 1⁴=3.