Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій

5)J(0,0,1)

6)Т(1,0)Приклад 9. МНР-програма для функцiї f(x)=[x/2]:

1)J(0,2,7)

2)S(2)

3)J(0,2,7)

4)S(2)

5)S(1)

6)J(0,0,1)

7)Т(1,0)

Приклад 10. МНР-програма для функцiї f(x)=sg(x):

1)J(0,1,4)

2)Z(0)

3)S(0)

Приклад 11. МНР-програма для функцiї f(x, y)=xy,

1)J(3,1,9)

2)J(0,2,6)

3)S(2)

4)S(4)

5)J(0,0,2)

6)Z(2)

7)S(3)

8)J(0,0,1)

9)Т(4,0)

2. МАШИНИ ТЬЮРIНГА

Пiд (детермінованою) машиною Тьюрiнга (скорочено МТ) будемо розумiти впорядковану 5-ку (Q,T,, q0 ,q*), де: