Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій
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*), де: