"lihtrekursiivseks" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

.,hm) = g(h1,..,hm) Rekursioon: n+1-kohaline f-n f on saadud n-kohalisest f.-nist g ning n+2-kohalisest f.-nist h rekursioonioperaatori rakendamisel, kui iga xi ja y korral kehtivad võrdused: f = R[g,h]: f(x1,..,xn,0) = g(x1,..,xn) f(x1,..,xn,y+1) = h(x1,..xn,y,f(x1,..,xn,y)) Algfunktsioonid: On(x1,..,xn) = 0 (n-kohaline konstant) s(x) = x+1 Inm (x1,..,xn) = xm (0lihtrekursiivseks, kui see on algfunktsioonidest superpositsiooni ja rekursioonioperaatori abil. Predikaat ­ f.-n, mille väärtuste piirkond on kahendväärtus. Kui g on arvutatav f.-n ja h1..hm on n-kohalised arvutatavad f.-nid, siis on ka f = Sm+1[g,h1,..,hm] arvutatav. Tõestus: eksisteerib registermasina programm Kui g on n-kohaline arvutatav f.-n ja h on n+2 kohaline arvutatav f.-n, siis f = R[g,h] on n+1-kohaline arvutatav f.-n. Tõestus: eksisteerib registermasina programm