"lihtrekursiivne" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

-ni ühegi alamklassi Fk korral,. Tõestus: Oletame vastuväiteliselt, et Fk-s leidub univ- f.-n U. U definitsiooni kohaselt saab moodustada f.-ni f(x1,..,xk) = g(U(x1,..,xk)), mis kuulub ka klassi F. U def kohaselt eksisteerib siis aga b, mille korral iga (x1,...,xk) jaoks U(b,x1,..,xk) = f(x1,..,xk). See kehtiks ka x1 = b korral: U(b,b,x2,..xk) = f(b,x2,..,x2) = g(U(b,b,x2,..,xk)) .. see on vastuolu selle z ei võrdu g(z)-ga. Lihtrekursiivsete f.-nide klassi U pole lihtrekursiivne: Tõestus: lihtrekursiivsed f.-nid on kõikjal määratud nende hulgas leidub s(x) = x+1, millle korral f.-nil pole püsipunkti Osaliselt rekursiivsete f.-nide klassi U on osaliselt rekursiivne 29. Ühekohaliste funktsioonide arvutatavus. Gödeli numbrid. Gödeli number: f.-ni h Gödeli number arvutatakse: 2, kui h = s 3, kui h = q G(h) = 5Gf * 7Gg, kui h = f + g 11Gf * 13Gg, kui h = f * g 17Gf, kui h = f-1 19Gf, kui h = if Gödeli f.-n kodeerib f