"hekohalised" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

b) pole määratud, vastasel juhul. Ehk y on esimene element, mille puhul g(x1,...,xn,y) = 0. Funktsiooni f esitatakse sel juhil operaatortermi abil selliselt: f = μy [g]. DEF: Osaliselt rekursiivsed funktsioonid on konstrueeritavad elementaarfunktsioonidest superpositsiooni-, rekursiooni- ja minimeerimisoperaatori abil. DEF: Kõikjal määratud rekursiivseid funktsioone nimetatakse täisrekursiivseteks funktsioonideks. 20 Cantori funktsioonid. Arvutatava funktsiooni ühekohalised esindajad. Cantori funktsioon (kahekohaline) seab igale naturaalarvude paarile vastavusse tema koodi: c(x,y) = 0,5(x +y)(x+y+1)+x. Leiduvad ka pöördfunktsioonid koodile vastava naturaalarvu leidmiseks. l(c(x, y)) = x; r(c(x, y)) = y c3(x,y,z) = c(x,c(y,z)) cm(x1,x2,...,xm) = c(x1,cm−1(x2,...,xm)) Funktsioonid cm,c1m,c2m,...,cmm on lihtrekursiivsed. Cantori numbreid kasutatakse registermasina käskude kodeerimiseks. Ülejäänud saab neist käskudest tuletada.