rekursi/o KompLeks

rekursio

MATKOMP Tia maniero difini funkcion aŭ komputan proceduron, ke la difinato eventuale povas referenci sin mem: senfina rekursio (ekz-e kaŭzita de cirkla difino).
SUB:rikuro1
Rim.: Kaj „rekursio“, kaj „rikuro“ etimologie signifas „retroiro“, t.e. reveno al la antaŭe komputitaj valoroj de iu vico por komputi la sekvan. Pri la termino „rekursio“ tiu koncepto ne plu validas: rekursia komputo povas anticipe ekzameni ankaŭ siajn „postajn“ valorojn, eĉ plenumi elĉerpan serĉon tra ili. Tion oni neniam faras en la klasika matematiko, por kies bezonoj plene sufiĉas rikuro, koncepto logike pli sekura. [Sergio Pokrovskij]
angle:
recursion senfina ~o: infinite recursion
beloruse:
рэкурсія senfina ~o: бясконцая рэкурсія
ruse:
рекурсия senfina ~o: бесконечная рекурсия

rekursia

MATKOMP Uzanta rekursion, karakterizata de rekursio: rekursia proceduro (programlingva proceduro2 kiu eventuale vokas sin mem dum la rultempo); SUB:rikura1
angle:
recursive ~a proceduro: recursive procedure
beloruse:
рэкурсіўны ~a proceduro: рэкурсіўная працэдура
ruse:
рекурсивный ~a proceduro: рекурсивная процедура

rekursia funkcio

MAT Unu el la matematikaj precizigoj de la intuicia koncepto pri komputeblo. Oni reduktas ĉiujn komputajn problemojn al naturnombraj funkcioj3 `N^n ->N`, kaj konstruas hierarkion el 3 subklasoj: primitive rekursiaj funkcioj, ĉieaj rekursiaj funkcioj, μ-rekursiaj funkcioj. La lasta klaso estas la plej ĝenerala, ĝi entenas la du aliajn kaj reprezentas ĉiujn komputeblajn funkciojn. Se oni diras simple „rekursia funkcio“, tiam oni celas ĝuste tiun ĉi klason: simbole la hierarkion de la rekursiaj funkcioj eblas prezenti per la formulo `"PRF" sub "ĈRF" sub "MRF"`; estas pruvite, ke la klaso da rekursiaj funkcioj, la klaso da funkcioj difineblaj per Turinga aŭtomato, per λ-kalkulo, per la Markovaj ĉenoj estas ĉiuj egalaj.
angle:
recursive function
beloruse:
рэкурсіўная функцыя
ruse:
рекурсивная функция

primitive rekursia funkcio, PRF

MAT La difino estas rikura1.b: oni difinas la bazan klason kaj du operatorojn. La bazaj funkcioj estas: la konstanta funkcio `O(x)=0`; la alkremento `S(x)=x+1`; la projekcioj `"Pr"[m,n](x_1,...x_n)=x_m,1 le m le n`. La operatoroj estas la kunligo2 kaj la primitiva rekursiilo. Primitive rekursia funkcio estas baza primitive rekursia funkcio aŭ rezulto de finifoja apliko de la operatoro(j): `S(S(x))` estas primitive rekursia funkcio ĉar ĝi estas kunligo de du alkrenentoj (ĝi ĵetas `x to x+2`); ĉiuj primitive rekursiaj funkcioj estas ĉieaj funkcioj; pliopo da nombroteoriaj funkcioj estas primitive rekursiaj funkcioj.
angle:
primitive recursive function
beloruse:
прымітыўна-рэкурсіўная функцыя
ruse:
примитивно-рекурсивная функция

primitiva rekursiilo

MAT Operatoro uzata en la difino de primitive rekursia funkcio, simila al nombrila iteracio; la formala difino estas rikura1.b. Estu `f` funkcio `n`-loka, kaj `g` funkcio `n+2`-loka; tiam apliko de primitiva rekursiilo al la paro da funkcioj `(f,g)` estas tia `n+2`-loka funkcio `h`, ke baze: `h(x_1,...,x_n,0)=f(x_1,...,x_n)`; kaj rikure: `h(x_1,...x_n,y+1)=g(x_1,...x_n,y,h(x_1,...,x_n,y))`. Estu `f(x)="Pr"[1,1](x)=x` kaj `g(x,y,z)=S("Pr"[2,3](x,y,z))=S(y)`. Tiam `h(0,x)=x` kaj `h(S(y),x)=g(y,h(y,x),x)=S(h(y,x))`. Sekve `h(0,1)=1, h(1,1)=S(h(0,1))=2, h(2,1)=S(h(1,1))=3`. Do, `h` estas 2-loka primitive rekursia funkcio, nome „adicio“.
angle:
primitive recursion
beloruse:
апэратар прымітыўнай рэкурсіі
ruse:
оператор примитивной рекурсии

μ-rekursia funkcio, MRF, parta rekursia funkcio

MAT Funkcio difinta per la samaj rimedoj, kiel la primitive rekursiaj funkcioj, plus la μ-operatoro de senbara serĉo: ĉar la minimumigo povas diverĝi, tial ne ĉiuj μ-rekursiaj funkcioj estas ĉieaj; ankaŭ nenie difinitaj (ĉie diverĝaj) funkcioj estas partaj rekursiaj funkcioj.
angle:
partial recursive function, >(μ-)recursive function
beloruse:
часткова рэкурсіўная функцыя
ruse:
частично рекурсивная функция

ĉiea rekursia funkcio, ĈRF

MAT μ-rekursia funkcio kiu estas ĉiea funkcio: ĉiu PRF estas ĉiea rekursia funkcio; ekzistas ĉieaj rekursiaj funkcioj kiuj ne estas primitive rekursiaj.
angle:
total recursive function
beloruse:
агульнарэкурсіўная функцыя
ruse:
общерекурсивная функция

administraj notoj

~o: Mankas dua fontindiko.
~o: Mankas fonto, kiu estas nek vortaro nek terminaro.
~a: Mankas dua fontindiko.
~a: Mankas fonto, kiu estas nek vortaro nek terminaro.
~a funkcio: Mankas dua fontindiko.
~a funkcio: Mankas fonto, kiu estas nek vortaro nek terminaro.
primitive ~a funkcio, PRF: Mankas dua fontindiko.
primitive ~a funkcio, PRF: Mankas fonto, kiu estas nek vortaro nek terminaro.
primitiva ~ilo: Mankas dua fontindiko.
primitiva ~ilo: Mankas fonto, kiu estas nek vortaro nek terminaro.
μ-~a funkcio, MRF, parta ~a funkcio: Mankas dua fontindiko.
μ-~a funkcio, MRF, parta ~a funkcio: Mankas fonto, kiu estas nek vortaro nek terminaro.
ĉiea ~a funkcio, ĈRF: Mankas dua fontindiko.
ĉiea ~a funkcio, ĈRF: Mankas fonto, kiu estas nek vortaro nek terminaro.