Sekvan paĝon! Antaŭan paĝon! Indekson! Instrukcion!

  1. La algoritmo: Pri la koncepto
  2. La rekursiaj funkcioj
  3. Universalaj rekursiaj funkcioj
  4. Aŭtomatoj: Manieroj difini algoritmon per abstrakta aŭtomato

La algoritmo

Intuicie la koncepto pri algoritmo, laŭ ĝia uzado en diversaj branĉoj de matematiko, havas la sekvajn trajtojn:
  1. ĝi konsistas el finia aro da precizaj preskriboj (ordonoj);
  2. ĝi operacias super precize difinita aro de eblaj enigaĵoj (argumentoj, donitaĵoj);
  3. ĝi produktas eligaĵon (rezulton) por ajna allasebla enigaĵo post finia nombro da paŝoj (paŝo estas plenumo de iu el la ordonoj);
  4. la algoritmo estas determinisma, t.e. ĉiun paŝon sekvas unike difinita sekva paŝo (aŭ halto).
Inter la bone konataj ekzemploj pri algoritmo menciindas: 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.

La rekursiaj 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.

  1. La bazaj komputeblaj funkcioj
  2. La substituo: Operatoro
  3. La primitiva rekursio: Operatoro
  4. La minimumigo: Operatoro

La bazaj komputeblaj funkcioj

Kutime oni elektas la plej simplajn, klare komputeblajn funkciojn:
konstanta funkcio
O(x) = 0
krementa funkcio
A(x) = x + 1
projekcio
Pr[m, n](x₁, … ,xn)=xm, 1≤m≤n

La substituo

Temas pri kompono ĵetanta n-lokan funkcion f kaj m-lokajn funkciojn g₁,…,gm al m-loka funkcio h, tiel ke

h(x₁,…,xn) = f(g₁(x₁,…,xm),…,gn(x₁,… xn))

La primitiva rekursio

Tiu operatoro ĵetas n-lokan funkcion f kaj n+2-lokan funkcion g al (unika) n+1-loka funkcio h tiel ke

h(x₁,…,xn,0) = f(x₁,…,xn)
 h(x₁,…,xn,y+1) = g(x₁,…,xn,h(x₁,…,xn,y))

La minimumigo

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:

h(x₁, …, xn) = µy[f(x₁,…,xn,y) = 0] 

  1. Senbara serĉo en Paskalo: La ĝenerala mu-operatoro
  2. Barita serĉo en Paskalo: La primitive rekursia speco
Senbara serĉo en Paskalo
En Paskalo la senbaran serĉon oni povus esprimi jene: 
   PROCEDURO mu(VAR y: entjera; 
                FUNKCIO g(yy:entjera; xx:vektoro); 
                x: vektoro); 
   STARTO y:=0; 
          DUM g(y,x)≠0 FARU y:=y+1 
   FINO

Barita serĉo en Paskalo
En Paskalo la primitive rekursian specon de la mu-operatoro por naturnombra funkcio f 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

Universalaj rekursiaj funkcioj

Por ajna loknombro n>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

f(x₁,…,xn) = Fn(e,x₁,…,xn), 

kie e estas la Godela numero de f.

Universalajn rekursiajn funkciojn komputas universalaj Turingaj aŭtomatoj.

Sekvan paĝon Indekson Instrukcion