"projektsioonifunktsioon" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

DEF: Lihtrekursiivsed funktsioonid on konstrueeritavad elementaarfunktsioonidest superpositsiooni- ja rekursioonioperaatori abil. Lihtrekursiivsed funktsioonid on kõikjal määratud. nt summa, korrutis, x!, sign Elementaarfunktsioonideks loetakse järgmised funktsioonid: • konstantne funktsioon On : Nn → N, mis iga väärtuste komplekti x1,...,xn ∈ N korral omab väärtust 0. • järgmise naturaalarvu funktsioon s : N → N, mis iga x ∈ N korral annab väärtuse s(x)=x+1; • projektsioonifunktsioon Inm : Nn → N, kus m <= n, mis iga väärtuste komplekti x1,...,xn ∈ N korral omab väärtust Inm(x1,...,xn) = xm. (valib n-st m-nda) DEF: (funktsioonide järjest rakendamine, liitfunktsioon) Funktsioon f on saadud funktsioonist g ja funktsioonidest h1,…,hm superpositsioonioperaatori Sm+1 abil, kui kõikide väärtuste x1,...,xn ∈ N korral kehtib seos f (x1,...,xn) = g(h1(x1,...,xn),...,hm(x1,...,xn)). Funktsiooni f esitatakse sel juhil operaatortermi