Algoritmo difinas ĵeton de
ĉiuj eblaj enigaĵoj al ĉiuj eblaj eligaĵoj; nature, oni rajtas nomi tian
ĵeton algoritma (algoritmohava) ĵeto, aŭ komputebla funkcio. Tamen oni ne
konfuzu la du nociojn, algoritmo kaj komputebla ĵeto: ja ĉiu algoritma
ĵeto havas malfinian (kvankam numereblan) aron da algoritmoj ĝin
komputantaj.
Per aritmetikigo oni
kutimas redukti studon de ajnaj algoritmaj ĵetoj al tiu pri naturnombraj
algoritmaj funkcioj.
Tradicia difino de rekursia funkcio uzas finian aron da bazaj
funkcioj kaj tri operatorojn.
La fermo de la bazaj funkcioj per ĉiuj tri operatoroj
formas la klason de rekursiaj funkcioj; la fermo per la du unuaj (sen la
minimumigo) formas la klason de la primitive rekursiaj funkcioj.
Operatoro de senbara serĉo, ĵetanta
rekursian funkcion f: ℕ₀n+1→ℕ al nova rekursia
funkcio h:ℕ₀ⁿ→ℕ tia, ke por ajnaj
x₁,…,xn, y la egalaĵo
h(x₁, …, xn) = y
veras SSE
f(x₁,…,xn,0), … f(x₁,…,xn,y−1)
estas
ĉiuj difinitaj kaj nenulaj, dum
f(x₁,…,xn,y)
estas difinita
kaj egalas al 0; se tia y malestas, la valoro de
h(x₁,…,xn) estas nedifinita. Simbole oni esprimas
minimumigon aplikante la mu-operatoron:
En Paskalo la primitive rekursian specon de la
mu-operatoro por naturnombra funkciof oni povas esprimi per la
FUNKCIO mu(FUNKCIO f(yy: entjera; xx: vektoro);
baro: vektoro): entjera;
VAR y: entjera;
STARTO
y := 0;
DUM (y≠baro) KAJ (g(y, x)≠0) FARU y := y + 1;
mu := y;
FINO
Por ajna loknombron>0 oni povas
indiki primitive rekursiajn funkciojn U: ℕ→ℕ kaj
Tn:ℕ₀n+2→ℕ tiajn, ke por ajna rekursia
funkcio f:ℕ₀n→ℕ ekzistas e∈ℕ (la Godela numero de f), veriganta la egalaĵon
f(x₁,…,xn) = U(µy[Tn(e,x₁,…,xn,y)=0])
El
tiu teoremo sekvas, i.a., unu el la pintaj rezultoj de la tuta teorio:
Por ĉiu klaso de n-lokaj rekursiaj funkcioj eblas konstrui
universalan funkcion n+1-lokan, t.e. tian rekursian
funkcion Fn, ke por ajna n-loka rekursia funkcio
f kaj por ĉiuj x₁,…,xn∈ℕ validu