rekursi/o KompLeks

rekursio   Vikipedio

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