Teoreetilibe informaatika kordamisküsimused
(n)Sm,n(ay) (z) = z a (c(y,z)),
kus y = cm(y1,..,ym) ja z = cn(z1,...,zn)
Sellisel korral on arvutatavad:
p (z) = c(0,z)
q(n) = (l(n) + 1,r(n)) = (c(y,z)) = c(y+1,z)
k(i,,j), kus k(i,j) = i o j
Olgu f konstrueeritud järgnevalt:
f = R[g,h], g() = p, h(x,y) = k(y,q)
f(0) = p
f(x+1) = k(f(x,q))
Siit näeme, et f(x)(y) = c(x,y)
Valime Smn = k(f(y),a), et teoreemi tingimused oleksid rahuldet':
Püsipunkt:
On s-n-m teoreemi järelduseks.
Mistahes arvutatava f.-ni h korral leidub selline naturaalarv u, et kehtib võrdus:
u = h(u)
Tõestus:
Osaliselt rekursiivsete f.-nide univ f.-n on arvutatav. Olgu selle Gödeli numbriks
U.
U(i,x) = i(x)
Defineerime g nii, et g(i)(x)=U(U(i,i),x)
s-n-m teoreemi põhjal on g arvutatav
31. Rice'i teoreem.
Arvutatavate f.-nide Gödeli numbrite iga mittetriviaalne (mittetühi ja
mitteuniversaalne) hulk on mittelahenduv.
Tõestus:
annaabi.ee 
