"rekursiivserd" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

Neist kahest järeldub, et kõik lihtrekursiivsed funktsioonid on arvutatavad. 25. Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid. Ütleme, et n-kohaline f.n f on saadud n+1-kohalisest funktsioonist g minimeerimisoperaatori y abil f = y[g] abil, kui kogu määramispiirkonnas y, kus y on min element, et g(x1,..xn,y) = 0, kusjuures iga zrekursiivserd funktsioonid: Funktsioonid, mis on algfunktsioonidest saadavad superpositsiooni-,rekursiooni ja minimeerimisoperaatori abil. Lihtrekursiivsed f.-nid on osaliselt rekursiivsed. Kõikjal määratud osaliselt rekursiivseid f.-ne nimetatakse üldrekursiivseteks f.- nideks. Operaatorterm: · funktsioonisümbol · avaldis kujul E(t1,t2,..tn), kus E on n-kohaline operaator ja ti on operaatortermid · muid op-terme pole Kui g on n-kohaline arvutatav f