"rekursiooniteoreem" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

,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 arvutat...