Вопрос 17. Определение машины Тьюринга

ai

∆

q_j

Конечная лента разбитая на ячейки + рабочая головка

Е=0,1,2,…..

Алфавит: А={a₀,a₁,….,a_n}

(внешн. алф-т машина)

Множество внутр. сос-й: Q={q₀,q₁,…,q_n}

q₀=>СТОП (работа машины заканч.)

Операции: -сдвиг головки влево

- // - // - вправо

- замена буквы в тек. Ячейке

Команды: a_iq_j ->

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

T=<A,Q,П>

П=

T(i,j)=

Работа машины Тьюринга есть изменение конф-ии, т.е. распр-ие букв, сост. головки, полож-ие тек. Ячейки

K₀,K₁,K₂…. – конфигурации

Машинное слово

М₁=α q_jq_i β

Вопрос 18. Основные машины Тьюринга.

1. А – перенос нуля

q₁001^x0 ׀≡> q₀01^x00

2. Б⁺ - сдвиг вправо

q₁a_i1^x0 ׀≡> a_i1^x q₀0

3. Б^- - сдвиг влево

01^x q₁ a_i ׀≡> q₀01^x a_i

4. В – транспозиция

q₁01^x01^y0 ≡> q₀01^y01^x0

5. К – кодирование

q₁01^x00x0 ׀≡> q₀01^x01^x0

6. Л – стирающая машина

q₁01^x0 ׀≡> q₀00^x0

7. R – удаление 1

q₁01^x+10 ׀≡> q₀01^x00

8. S – добавление 1

q₁01^x0 ׀≡> q₀01^x+1

9. Сложение

q₁01^x+101^y+10 ׀≡> q₀01^x+y+1000

10. Умножение

q₁01^x+101^y+10 ≡> q₀01^x*y+10

Операции над машинами Тьюринга.

1. Т=Т₁◦Т₂ – композиция машин

М₁ =^Т1> М₂ = α q₀^T1 _β

α q₀^T2 _β = [М₂]^{q0 T1} _{q0 T2} =^Т2> М₃

М₁=^Т> М₃

Q₁∩Q₂ = Ø, A₁=A₂=A

T=<A, (Q₁\{q₀^T1})UQ₂, [П₁]^{q0 T1} _{q0 T2}U[П₂]>

- последвательное выполнение

2. Условный оператор

Т₁, Т₂

Т=Е{^T1_T2

1. αq₁^Tabc β, abc=010 и αq₁^T1abc β = M₁, то αq₁^Tabc β =^Т>М₁

2. если abc≠010 и αq₁^T2abc β = М₂, то αq₁^Tabc β =^Т>М₂

Q₁∩Q₂ ≠ Ø, A₁=A₂=A

T=<A, (Q₁\{q₀^T1})U(Q₂\{q₀^T2})U{q₀^T, … , q_r^T}, П>

П=(П₁ ^{q0 T1}_{q0 T2} )U(П₂ ^{q0 T2}_{q0 T1})U {проверка условия и задание альтернатив}

3. Условный оператор с циклом

Т₁, Т₂, Т₃

• {Т₂, если авс=010

Т=Т₁ Е {

{Т₃ в прот. случае

Работает Т₁

М₁ = > αq₁^T1abc β

Проверка условия (заменяем q₀^T1 на q₂).

После работы T₂ следует остановка.

После работы Т₃ переход к Т₁ и цикл повторяется, q₀^T3 заменяется на q₁^T1,

а q₀^T2 на q₀^T.

Вопрос 19. Вычисление функций на машинах Тьюринга.

f: X→ N , XN^K. f называется вычислимой на машине Тьюринга T_f, если:

1) (n₁,…,n_k)  X, q₁^Tf 0n₁ 0n₂ 0 … 0n_k ^ (Машина работает бесконечно, т.е. не переходит в q₀^Tf )

n=11…1  n+1 раз.

2) (n₁,…,n_k)  X, то q₁^Tf 0n₁ 0n₂ 0 … 0n_k 0 ^Tf  q₀^Tf 0 f (n₁,…,n_k) 0 

f правильно вычислима на М.Т. T_f если выполняется 1), 2) и не достраиваются ячейки слова.

Примеры:

1) x+y и x  y – правильно вычислимы на М.Т.

2) Если f, q₁,…,q_n правильно вычислимы, то f(q₁(x₁,…,x_k),q₂(x₁,…,x_k),…,q_n(x₁,…,x_k)) правильно вычислима.

f (g₁(x₁,x₂,x₃), g₂(x₁,x₂,x₃)).

q₁ 0 x₁ 0 x₂ 0 x₃ 0 ^К3

q₂ 0x₁ 0x₂ 0x₃ 0 x₁ 0x₂ 0x₃ 0 (Б⁺)³Tq₁

0x₁ 0x₂ 0x₃ q_ 0 q₁(x₁,x₂,x₃) 0 (Б^-)³Ц₄

q_ 0 g₁ (x₁,x₂,x₃) 0 g₂(x₁,x₂,x₃) 0 (Б⁺)Tq₂Б^-

q₀ 0 f(g₁(x₁,x₂,x₃),g₂(x₁,x₂,x₃)) 0