Teoreetilibe informaatika kordamisküsimused
Kui superpositsioonioperaatori suhtes kinnine f.-nide klass sisaldab korteezhide
kodeerimise ja dekodeerimise f.-ne cm,c1m, cmm, siis selle klassi iga m-kohalise f.-
ni f jaoks leidub samasse klassi kuulub ühekohaline esindaja ühe muutuja f.-n,
nii, et iga esialgse f.-ni argumentvektori korral kehtib:
f(x1,..xn) = g(cm(x1,..,xn))
Tõestus:
Iga n = cm jaoks kehtib seos g(n) = f(c1m,..,cmm)
Ühekohaliste esindajate leidmiseks peame sisse tooma 4 operaatorit:
Kõik peab kehtia kõigi argumentvektorite korral
Liitmisoperaator:
h(x) = f(x) + g(x)
h=fog
Kompositsioonioperaator:
h(x) = g(f(x))
f=f*g
Pööramisoperaator:
h(x) = z[f(z) - x]
h = f-1
Lahutamistehe on määratud, kui f(z)>= x
Iteratsioonioperaator:
h(x) = f(f(...f(0)...)) rekursiivne pöördumine kuni nullini.
h = if
28. Arvutatavate funktsioonide klassi universaalne funktsioon.
k+1-kohalist f.-ni U nimetatakse f.-nide klassi alamklassi (klassi F k-argumendiga
klassid) Fk universaalseks f
annaabi.ee 
