"iteratsioonioperaatoreid" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

Gödeli f.-n kodeerib f.-ni tuletusele vastava operaatortermi. N-kohalise f.-ni Gödeli numbriks on tema ühekohalise esindaja Gödeli number. Ühele f.-nile võib leida mitu Gödeli numbrit (kuna tuletusi algf.-nidest võib olla mitu), üks Gödeli number vastab alati kindlale f.-nile. Arvutatavus: Robinsoni teoreemid: I Kõik ühekohalised lihtrekursiivsed f.-ni on arvutatavad algf.-nidest s(x) = x+1 ja g(x) = |x ­ (floor(sqrt(x)))2| (ruutjääk), kasutades liitmise, kompositsiooni- ja iteratsioonioperaatoreid II Kõik ühekohalised osaliselt rekursiivsed f.-nid on saadavad algf.-nidest s(x) = x+1 ja g(x) = |x ­ (floor(sqrt(x)))2| (ruutjääk), kasutades liitmise-, kompositsiooni- ja pööramisoperaatoreid. 30. Kleene' s-n-m-teoreem ja püsipunktiprintsiip. N-kohalise f.-ni Gödeli numbriks on tema ühekohalise esindaja Gödeli number. a ühekohaline f.-n, mille Gödeli number olgu a. g olgu f ühekohaline esindaja. Kehib seos: f = a(n) = cn g o Kuna f (x1,.