Кодировка машин Тьюринга.

Кодом машины Тьюринга называется запись набора её команд в алфавите {*,1}, позволяющая однозначно восстанавливать каждую команду. T=(A,S,,μ,); Покажем, что любую машину можно закодировать:

A={a₁,... a_n};

S={s₀,s₁...s_m};

N(П)=1;

N(Л)=1²;

N{Н}=1³;

N(s₀)=1⁴;

N(s₁)=1⁵;

...

N(s_n)=1ⁿ⁺⁴;

N(a₁)=1ⁿ⁺⁵;

...

N(a_m)=1^n+m+4.

(s_i, a_k)( a_j, D, s_p), где D – управляющий символ, a_j – что печатать, s_p – следующее состояние.

N(s_i, a_k)= N(s_i)*N(a_k)* N(a_j)*N(D)*N(s_p) – код команды.

N(T)= N(s₁, a₁)**N(s₂, a₁)**..**N(s_n, a_m).

Машина Тьюринга называется самоприменимой, если она применима к собственному коду, т.е переходит в состояние s₀ при работе с ним.

Алгоритмически неразрешимые проблемы.

Проблема самоприменимости:

• Существует ли алгоритм, который для любой машины Тьюринга позволяет выяснить, является ли эта машина самоприменимой или нет.

• Существует ли такая машина Тьюринга L, применимая к коду N(T) произвольной машины, что в своем заключительном состоянии L зависает над 0, если T – несамоприменима, и над 1 – если она самоприменима

Теорема (об алгоритмической неразрешимости проблемы самоприменимости): не существует такой машины L, которая решала бы проблему самоприменимости.

Док-во: Допустим, что машина L существует. На базе L составим машину L такую, что в L войдут все команды из L, но вводится новое состояние s₀, которое и будет заключительным состоянием L. В список команд введем еще две: (s₀,)(s₀,Н,) и (s₀,1)(s₀,Н,1).

Мы получили машину L, которая обладает следующими свойствами:

1. неприменима к коду самоприменимых машин;

2. применима к коду несамоприменимых машин.

Запустим L на собств. кодом N(L):

Если L остановится, значит L самоприменима  L применима к коду самоприменимых машин, возникает противоречие.

Если L не остановится значит L несамоприменима  L неприменима к коду несамоприменимых машин, возникает противоречие.

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

Проблема применимости.

Проблема применимости:

• Существует ли алгоритм, который для любых машины Тьюринга Т и слова β позволяет выяснить, является ли эта машина применимой к β или нет.

• Существует ли машина L, применимая ко всем словам вида N(T)λβ, где N(T) – код произвольной машины Т, а β – произвольное слово, такая, что в своем заключительном состоянии L зависает над 0, если T – не применима к β, и над 1 – если она применима к β.

Напишем программу работы машины T₁, которая применима к любому слову вида x₁, x₂,…, x_n, и дублирует это слово через λ: x₁, x₂,…, x_n λ x₁, x₂,…, x_n, а по окончании работы возвращается в начало.

	1	2	3	4	5	6	7
λ	λ Л 7	λ П 3	a Л 4	λ Л 4	λ П 6	b Л 4	λ П 0
a	a П 2	a П 2	a П 3	a Л 4	a П 5	a П 6	a Л 7
b	b П 5	b П 2	b П 3	b Л 4	b П 5	a П 6	b Л 7
a				a П 1
b				b П 1

Проверим для слова aba.

a ba	a b a	a b a	a b a λ	a b a λ λ	a b a λ a	a b a λ a...	a b a λ a
1	2	2	2	2	4	4	4
a b a λ a	a b a λ a	a b a λ a	a b a λ a	a b a λ a λ	a b a λ a b	aba λ ab...	a b a λ a b
1	5	5	6	6	4	4	4
a b a λ a b	a b a λ ab	a b a λ a b	a b a λ a b	abaλ a b λ	abaλaba...	ab a λaba	a b a λ aba
1	2	3	3	3	4	4	1
a b a λ aba	a b a λ aba	a b a λ aba	λ abaλaba	a baλaba
7	7	7	7	0

Теорема (об алгоритмической неразрешимости проблемы применимости): не существует такой машины L, которая решала бы проблему применимости.

Док-во: Пусть существует машина L, которая решает проблему применимости. Построим машину L такую, что она будет включать в себя все команды L и Т₁: L= Т₁ ºL – т.е. с начла работает Т₁, а затем L.

Напишем на ленте код N(T₁) и запустим L: N(T₁)→ N(T₁) λ N(T₁). Мы получили, что L решает проблему самоприменимости, что противоречит теореме об алгоритмической неразрешимости проблемы самоприменимости. Таким образом, предположение, что существует машина L – неверно. ч.т.д.