"elementaarfunksioonid" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

abil järgmiselt: f = Sm+1[ g, h1,…, hm] (h-sid m tk + g = m+1 funktsiooni) DEF: (funktsiooni väärtust kasutatakse iseenda argumendina) Funktsioon f on saadud funktsioonist g ja funktsioonidest h rekursioonioperaatori R abil, kui kõikide väärtuste x1,...,xn ∈ N ja y ∈ N korral kehtivad seosed f(x1,…,xn,0) = g(x1,...,xn) ja f(x1,...,xn,y+1) = h( x1,…,xn, y, f(x1,…,xn,y) ). f =R[g,h] Teoreem: Rekursiivsed funktsioonid on Turingi masinal arvutatavad. T: Elementaarfunksioonid Registermasinal: On =0 on CLR, s(x)=x+1 on INC, Inm= xm on R → R. Ja ka Sm+1, R ja μy on reg.masinal arvutatavad. Neist saab konstrueerida kõik rek. funktsioonid. Ja reg.masin ja TM lahendavad samu asju. Teoreem: Iga registermasinal realiseeritav funktsioon on (osaline) rekursiivne funktsioon. 
 Seega: Osaliselt rekursiivsete funktsioonide hulk langeb kokku Turingi mõttes arvutatavate funktsioonide hulgaga. 19 Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid.