Rekursiooni ja keerukusteooria eksami konspekt
23 Kleene' s-m-n teoreem.
Ühe funktsiooni Gödeli numbrist teise f.-ni Gödeli numbri arvutamine.
Teoreem: Leidub selline m+1-kohaline (m y-t ja a) arvutatav funktsioon Snm, et suvaliste a,y1,...,ym korral
kehtiks
T: esitame selle ühekohaliste esindajate kaudu, kus y = cm(y1,…,ym) ja z = cn(z1,…,zn) muutujad:
Siis on arvutatavad:
Olgu funktsioon R(x) konstrueeritud järgmiselt:
Näeme, et kehtib võrdus φR(x)(y) = c(x,y).
24 Rekursiivsete funktsioonide püsipunktiprintsiip.
See on Kleene’i rekursiooniteoreem, mis on s-m-n teoreemi järelduseks.
Alati on selline püsipunkt x, et f(x) = x. Need on sellised punktid, mille poole koonuvad kõik funktsiooni
lahendid. Iga arvutatava funktsiooni jaoks leidub naturaalarv u nii, et: φu = φh(u)
T: Osaliselt rekursiivsete f.-nide universaalne funktsioon 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.
annaabi.ee 
