"iteratsioonioperaatorit" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

• pööramine: h = f −1 ∀n[ h(n) = μz [f(z)−n] ] • iteratsioon: h = ιf ∀n[ h(n) = fn(0) ], kus n > 0 DEF: Funktsiooni h teatud formaalses keeles esitatud kirjeldusele vastavusse seatud unikaalset naturaalarvu Gh nimetatakse selle funktsiooni Gödeli numbriks. Teoreem: Kõik ühekohalised lihtrekursiivsed funktsioonid on genereeritavad elementaarfunktsioonidest s(n)=n+1 ja q(n)=n−⌊√n⌋2 („ruutjääk”), kasutades liitmise, kompositsiooni- ja iteratsioonioperaatorit. Teoreem: Kõik ühekohalised osalised rekursiivsed funktsioonid on genereeritavad elementaarfunkt- sioonidest s(n) = n+1 ja q(n) = n−⌊√n⌋2, kasutades liitmise, kompositsiooni- ja pööramisoperaatorit. DEF: Funktsioonile h vastavusse seatud naturaalarv Gh (tema Gödeli number) arvutatakse nii: 2, kui h=s (s(n)=n+1) 3, kui h=q (q(n)=n−⌊√n⌋2) 5Gf · 7Gg, kui h=f+g 11Gf · 13Gg, kui h=f◦g 17Gf, kui h=f -1 19Gf, kui h=ιf