Reja: tyuring mashinasi. Tyuring tezisi. Markov algoritmi

Y=F(X1, X2,…, Xn) qisman sonli musbat funktsiya deyiladi, agarda: 1) D(Y) N ×∙ N∙×…×∙N = ;
2) E(Y) N
Quyidagi sonli funktsiyalar biz oddiy deb nomlaymiz:
1) O(X)=0 – nol funktsiya
2)  (X1, X2,…, Xn)=Xm , 1≤ M≤ N – o’zining agumentlarini qaytaruvchi funktsia;
3) S(X)=X+1 – kelib chiqish funktsiyasi.
Biz quyidagi uchta operatsiyani aniqlaymiz: superpozitsiya, ibtidoiy rekursiya va minimallashtirish.
Superpozitsiya ishlashi
N - bu mahalliy funktsiya, deb aytamiz φ u M - mahalliy funktsiya ψ va N - mahalliy funktsiyalar F1, F2,…, Fm superpozitsiya operatsiyasi yordamida olinadi, agar barcha X1, X2,…, Xn uchun quyidagi tenglik bo'lsa:
φ (X1, X2,…, Xn) = ψ (F1 (X1, X2,…, Xn),…, Fm (X1, X2,…, Xn))
Ibtidoiy rekursion operatsiya
(N + 1) mahalliy funktsiya deb aytamiz F Bu N - mahalliy funktsiyadan va (N + 2) - mahalliy H funktsiyasidan ibtidoiy rekursiya operatsiyasi yordamida olinadi, agar X1, X2, ..., Xn qiymatlari uchun tengliklar bajarilsa:
F (x1, x2,…, xn, 0) = g (x1, x2,…, xn)
F (x1, x2,…, xn, 1) = h (x1, x2,…, xn, 0, f (x1, x2,…, xn, 0))
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
F (x1, x2,…, xn, y + 1) = h (x1, x2,…, xn, y, f (x1, x2,…, xn, y)))
Ushbu tengliklar ibtidoiy rekursiya sxemasi deb ataladi. Va F funktsiyani ibtidoiy rekursiya operatsiyasi yordamida G, H C funktsiyalaridan olinganligi quyidagicha yoziladi: F = R (G, H).
Ta'rif 1. F funktsiyasi ibtidoiy rekursiv funktsiya deb ataladi, agar u har qanday ketma-ketlikda sonli marta olingan superpozitsiya va ibtidoiy rekursiya operatsiyalari yordamida eng oddiy funktsiyalardan olingan bo'lsa.
Ushbu ta'rif har qanday ibtidoiy rekursiv funktsiya raqamli funktsiya ekanligini anglatadi.
Barcha ibtidoiy rekursiv funktsiyalar to'plami Pn.P bilan belgilanadi.
1-misol.
F (X, Y) = X + Y funktsiyaning ibtidoiy rekursiv ekanligini isbotlang.
Haqiqatan ham. Quyidagi identifikatorlar amal qiladi
F (X, 0) = X + 0 = X = G (X)
F (x, y + 1) = x + (y + 1) = (x + y) +1 = f (x, y) +1
Shundan kelib chiqadiki
X + Y = R (G (X) = X, H (X, Y, Z) = Z + 1)
G, H funktsiyalari eng sodda funktsiyalar bo'lgani uchun X + Y Pn.P.

2-misol.
F (X, Y) = X ∙ Y funktsiya ibtidoiy rekursiv ekanligini isbotlang.

Haqiqatan ham. Quyidagi identifikatorlar amal qiladi:
F (X, 0) = X ∙ 0 = 0 = G (X)
F (X, Y + 1) = X (Y + 1) = Xy + X = F (X, Y) + X
Shundan kelib chiqadiki
X + Y = R (G (X) = 0, H (X, Y, Z) = Z + X)
Birinchi misoldan kelib chiqadiki H(X,Y,Z)=X+Z  Pn.P. Demak bu? Xy  Pn.P.
Funktsiyani ko'ramiz: 
X Y=
Ushbu funktsiya qisqartirilgan farq deb ataladi.
3-misol.
F (X, Y) = X Y funktsiyasi ibtidoiy rekursiv ekanligini ko'rsating.
Birinchidan, X 1 funktsiyasi ibtidoiy rekursiv ekanligini unutmang. Haqiqatan ham:
0 1 = 0 = G (X)
(X + 1) 1 = X = H (X, Y)
Demak,
X 1=R(G(X)=0,H(X,Y)=X).
Bundan, X 1 Pn.P.

Bundan tashqari, qisqartirilgan farqning ta'rifiga asoslanib, ushbu funktsiyalar tenglikni qondirishini ko'rsatish oson:

X 0 = x = g (x)
x (y + 1) = (x Y) 1 = h (x, y, x Y)
Har qanday X va Y uchun bu identifikatorlar shuni ko'rsatadiki
X Y = R (g (x) = 0, h (x, y, z) = z a)
Funksiya H (X, Y, Z) = Z a Pn.P. bo'lgani uchun, X Y Pn.P.
Har qanday ibtidoiy rekursiv funktsiya raqamli funktsiya bo'lgani uchun, X - Y Pn.P.


X 0=x=g(x)
x (y+1)=(x Y)  1=h(x, y,x Y)
Ixtiyoriy X va Y. Berilgan tengliklar quyidagini ko’rsatadi,
X Y=R(g(x)=0, h(x, y,z)=z  α)
Funktsiya H(X,Y,Z)=Z α  Pn.P bo’lsa., unda X Y  Pn.P.
Ixtiyoriy primitive rkursiv funktsiya sonli funktsiya hisoblanadi, demak, , unda X–Y  Pn.P.

•