UUS kiire ja vahendustasuta krüptoraha NANO Teeni tasuta NANO Sulge
Facebook Like
Add link

"rekursiooniteoreem" - 1 õppematerjal

24
pdf

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

Informaatika - Tallinna Tehnikaülikool
75 allalaadimist


Registreeri ja saadame uutele kasutajatele
faili e-mailile TASUTA

Konto olemas? Logi sisse

Faili allalaadimiseks, pead sisse logima
või
Kasutajanimi / Email
Parool

Unustasid parooli? | Tee tasuta konto

Sellel veebilehel kasutatakse küpsiseid. Kasutamist jätkates nõustute küpsiste ja veebilehe üldtingimustega Nõustun