Решение. Задание 1.Найти результат применения машины Тьюринга к записи на ленте

Задание 1. Найти результат применения машины Тьюринга к записи на ленте.

1) q ₁1→ q ₁1 R

q ₁0→ q ₂1 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0 R.

K: 01111 10

_q1

2) q ₁1→ q ₁1 R

q ₁0→ q ₂1 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0 R.

K: 01101 0

_q1

3) q ₁1→ q ₁1 R

q ₁0→ q ₂1 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0 R.

K: 0 1 0000110

_q1

4) q ₁1→ q ₁1 R

q ₁0→ q ₂1 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0 R.

K: 01 11010

_q1

5) q ₁1→ q ₁1 R

q ₁0→ q ₂ 0R

q ₂1→ q ₃1 R

q ₂0→ q ₂ 0R

q ₃1→q₃1 R

q ₃0→ q ₀0.

K: 1 11001

_q1

6) q ₁1→ q ₁1 R

q ₁0→ q ₂ 0R

q ₂1→ q ₃1 R

q ₂0→ q ₂ 0R

q ₃1→q₃1 R

q ₃0→ q ₀0.

K: 1 1001101

_{q 1}

7) q ₁1→ q ₁1 R

q ₁0→ q ₂ 0R

q ₂1→ q ₃1 R

q ₂0→ q ₂ 0R

q ₃1→q₃1 R

q ₃0→ q ₀0.

K: 1 00001

_{q 1}

8) q ₁1→ q ₁1 R

q ₁0→ q ₂ 0R

q ₂1→ q ₃1 R

q ₂0→ q ₂ 0R

q ₃1→q₃1 R

q ₃0→ q ₀0.

K: 1 10011

_{q 1}

9) q ₁1→ q ₂1 R

q ₁0→ q ₁ 0R

q ₂1→ q ₁0 R

q ₂0→ q ₃ 0L

q ₃1→ q ₂1 L

q ₃0→ q ₀0.

K: 1 11101

_{q 1}

10) q ₁1→ q ₂1 R

q ₁0→ q ₁ 0R

q ₂1→ q ₁0 R

q ₂0→ q ₃ 0L

q ₃1→ q ₂1 L

q ₃0→ q ₀0.

K: 1 1111

_{q 1}

11) q ₁1→ q ₂1 R

q ₁0→ q ₁ 0R

q ₂1→ q ₁0 R

q ₂0→ q ₃ 0L

q ₃1→ q ₂1 L

q ₃0→ q ₀0.

K: 110101

_{q 1}

12) q ₁1→ q ₂1 R

q ₁0→ q ₁ 0R

q ₂1→ q ₁0 R

q ₂0→ q ₃ 0L

q ₃1→ q ₂1 L

q ₃0→ q ₀0.

K: 110011

_q1

13) q ₁1→ q ₀1

q ₁0→ q ₂0 R

q ₂1→ q ₂1 R

q ₂0→ q ₀1.

K: 01110

_q1

14) q ₁1→ q ₀1

q ₁0→ q ₂0 R

q ₂1→ q ₂1 R

q ₂0→ q ₀1.

K: 011010

_q1

15) q ₁1→ q ₀1

q ₁0→ q ₂0 R

q ₂1→ q ₂1 R

q ₂0→ q ₀1.

K: 0111110

_q1

16) q ₁1→ q ₀1

q ₁0→ q ₂0 R

q ₂1→ q ₂1 R

q ₂0→ q ₀1.

K: 0110110

_q1

17) q ₁1→ q ₁1 R

q ₁0→ q ₂0 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0.

K: 110011

_q1

18) q ₁1→ q ₁1 R

q ₁0→ q ₂0 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0.

K: 110101

_{q 1}

19) q ₁1→ q ₁1 R

q ₁0→ q ₂0 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0.

K: 111101

_{q 1}

20) q ₁1→ q ₁1 R

q ₁0→ q ₂0 L

q ₂1→ q ₂1 L

q ₂0→ q ₀0.

K: 11111

_{q 1}

2. Построить машину Тьюринга, правильно вычисляющую функцию.

1. ¦(x) =
2. ¦(x) = 2^x-1
3. 
4. 
5. ¦(x) =
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 

3.Найти функцию ¦(x,y), получаемые из с помощью операции примитивной рекурсии.

ОПРЕДЕЛЕНИЕ. Говорят, что (n+1)- местная функция φ получена из n-местной функции f и (n+2)-местной функции g с помощью оператора примитивной рекурсии, если для любых х₁,…,х_n, усправедливы равенства:

φ (x₁,…,x_n)

φ(x₁…x_n, y+1)= g(x₁…x_n,y))

Здесь важно отметить то, что независимо от числа аргументов в φ, рекурсия ведется только по одной переменной У; остальные n переменных х₁,…,х_n, на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров. Кроме того, схема примитивной рекурсии выражает каждое значение определяемой функции φ не только через данные функции f и g, но и через так называемые предыдущие значения определяемой функции φ прежде чем получить значение φ(х₁,…,х_n, k),придется проделать k+1 вычисление по указанной схеме- для У=0,1,…,k.

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10.