rekursi⁽⁺⁾·/·o

rekursi⁽⁺⁾·o

          Tia manier⭑·o difin⭑·i funkci¹·on aŭ⭑ komput⁹·an procedur²·on, ke⭑ la⭑
          difin⭑·at·o eventual¹·e pov⭑·as referenc³·i si·n mem⭑: sen·fin⭑·a rekursi⁽⁺⁾·o
          (ekz-e kaŭz⭑·it·a de⭑ cirkl⁸·a difin⭑·o).

   {rikur⁽⁺⁾·o^1}
   Rim.: Kaj⭑ „rekursi⁽⁺⁾·o“, kaj⭑ „rikur⁽⁺⁾·o“ etimologi²·e signif⭑·as „retroir⁽⁺⁾·o“, t.e.
   re·ven⭑·o al⭑ la⭑ antaŭ⭑·e kom⭑-put⭑·it·aj valor⭑·oj de⭑ iu vic⭑·o por⭑ komput⁹·i la⭑
   sekv⭑·an. Pri⭑ la⭑ termin⭑·o „rekursi⁽⁺⁾·o“ tiu koncept²·o ne⭑ plu⭑ valid⁴·as: rekursi⁽⁺⁾·a
   komput⁹·o pov⭑·as anticip³·e ekzamen⭑·i ankaŭ⭑ si⭑·ajn „post⭑·ajn“ valor⭑·ojn, eĉ⭑
   plen⭑·um·i {el·ĉerp⭑·an serĉ⭑·on} tra⭑ ili. Tio·n oni neniam⭑ far⭑·as en⭑ la⭑ klasik¹·a
   matematik¹·o, por⭑ kies⭑ bezon⭑·oj plen⭑·e sufiĉ⭑·as rikur⁽⁺⁾·o, koncept²·o logik¹·e pli⭑
   sekur⁴·a.

rekursi⁽⁺⁾·a

          Uz⭑·ant·a rekursi⁽⁺⁾·on, karakteriz¹·at·a de⭑ rekursi⁽⁺⁾·o: rekursi⁽⁺⁾·a procedur²·o
          (program¹+lingv⭑·a {procedur²·o^2} kiu eventual¹·e vok⭑·as si·n mem⭑ dum⭑ la⭑
          rul⭑-temp⭑·o); {rikur⁽⁺⁾·a^1}

rekursi⁽⁺⁾·a funkci¹·o

          Unu⭑ el⭑ la⭑ matematik¹·aj preciz⭑·ig·oj de⭑ la⭑ intuici⁽⁺⁾·a koncept²·o pri⭑
          {komput⁹-ebl⭑·o} . Oni redukt⁴·as ĉiu·jn komput⁹·ajn problem¹·ojn al⭑
          {natur⭑+nombr⭑·aj} {funkci¹·oj^3}  , kaj⭑ konstru⭑·as hierarki³·on el⭑
          3 sub·klas⭑·oj: {primitiv²·e rekursi⁽⁺⁾·aj funkci¹·oj} , {ĉie⭑·aj rekursi⁽⁺⁾·aj
          funkci¹·oj} , {μ-rekursiaj funkci¹·oj} . La⭑ last⭑·a klas⭑·o est⭑·as la⭑
          plej⭑ ĝeneral¹·a, ĝi en·ten⭑·as la⭑ du⭑ ali⭑·ajn kaj⭑ reprezent⭑·as ĉiu·jn
          komput⁹-ebl⭑·ajn funkci¹·ojn. Se⭑ oni dir⭑·as simpl⭑·e „rekursi⁽⁺⁾·a funkci¹·o“,
          tiam⭑ oni cel⭑·as ĝust⭑·e tiu·n ĉi⭑ klas⭑·on: simbol¹·e la⭑ hierarki³·on de⭑ la⭑
          rekursi⁽⁺⁾·aj funkci¹·oj ebl⭑·as prezent⭑·i per⭑ la⭑ formul¹·o  ; est⭑·as pruv⭑·it·e, ke⭑ la⭑ klas⭑·o da⭑ rekursi⁽⁺⁾·aj funkci¹·oj, la⭑
          klas⭑·o da⭑ funkci¹·oj difin⭑·ebl·aj per⭑ Turing⁽⁺⁾·a aŭtomat¹·o, per⭑
          λ-kalkulo, per⭑ la⭑ Mark⭑+ov⭑·aj ĉen⭑·oj est⭑·as ĉiu·j egal⭑·aj.

primitiv²·e rekursi⁽⁺⁾·a funkci¹·o, PRF

          La⭑ difin⭑·o est⭑·as {rikur⁽⁺⁾·a^1.b} : oni difin⭑·as la⭑ baz¹·an klas⭑·on kaj⭑
          du⭑ {operator⁽⁺⁾·ojn} . La⭑ baz¹·aj funkci¹·oj est⭑·as: la⭑ konstant⭑·a funkci¹·o
           ; la⭑ {al·krement⁽⁺⁾·o}  ; la⭑ {projekci¹·oj}
           . La⭑ operator⁽⁺⁾·oj est⭑·as la⭑
          {kun·lig⭑·o^2} kaj⭑ la⭑ {primitiv²·a rekursi⁽⁺⁾·il·o} . Primitiv²·e rekursi⁽⁺⁾·a
          funkci¹·o est⭑·as baz¹·a primitiv²·e rekursi⁽⁺⁾·a funkci¹·o aŭ⭑ rezult²·o de⭑
          fini⁽⁺⁾+foj⭑·a aplik³·o de⭑ la⭑ operator⁽⁺⁾·o(j):  est⭑·as primitiv²·e
          rekursi⁽⁺⁾·a funkci¹·o ĉar⭑ ĝi est⭑·as kun·lig⭑·o de⭑ du⭑ al·kren⭑-ent⁽⁺⁾·oj (ĝi
          ĵet⭑·as  ); ĉiu·j primitiv²·e rekursi⁽⁺⁾·aj funkci¹·oj est⭑·as {ĉie⭑·aj
          funkci¹·oj} ; pliopo da⭑ nombr⭑·o-teori⭑·aj funkci¹·oj est⭑·as primitiv²·e
          rekursi⁽⁺⁾·aj funkci¹·oj.

primitiv²·a rekursi⁽⁺⁾·il·o

          {Operator⁽⁺⁾·o} uz⭑·at·a en⭑ la⭑ difin⭑·o de⭑ {primitiv²·e rekursi⁽⁺⁾·a funkci¹·o} ,
          simil⭑·a al⭑ {nombr⭑·il·a iteraci⁽⁺⁾·o} ; la⭑ formal²·a difin⭑·o est⭑·as
          {rikur⁽⁺⁾·a^1.b} . Est⭑·u  funkci¹·o  - {lok⭑·a} , kaj⭑  funkci¹·o
           -lok⭑·a; tiam⭑ aplik³·o de⭑ primitiv²·a rekursi⁽⁺⁾·il·o al⭑ la⭑ par⭑·o da⭑
          funkci¹·oj  est⭑·as tia  -lok⭑·a funkci¹·o  , ke⭑ _baz¹·e:_
           ; kaj⭑ _rikur⁽⁺⁾·e:_
           .
          Est⭑·u  kaj⭑ 
          . Tiam⭑  kaj⭑ 
          . Sekv⭑·e  . Do⭑,
           est⭑·as {2-lok⭑·a} primitiv²·e rekursi⁽⁺⁾·a funkci¹·o, nom⭑·e „adici²·o“.

μ-rekursia funkci¹·o, MRF, part⭑·a rekursi⁽⁺⁾·a funkci¹·o

          Funkci¹·o di⭑+fint⁽⁺⁾·a per⭑ la⭑ sam⭑·aj rimed⭑·oj, kiel⭑ la⭑ {primitiv²·e
          rekursi⁽⁺⁾·aj funkci¹·oj} , plus⁸ la⭑ μ- {operator⁽⁺⁾·o} de⭑ {sen·bar⭑·a serĉ⭑·o}
          : ĉar⭑ la⭑ minimum³·ig·o pov⭑·as diverĝ⁽⁺⁾·i, tial⭑ ne⭑ ĉiu·j μ-rekursiaj
          funkci¹·oj est⭑·as ĉie⭑·aj; ankaŭ⭑ nenie difin⭑·it·aj (ĉie diverĝ⁽⁺⁾·aj)
          funkci¹·oj est⭑·as part⭑·aj rekursi⁽⁺⁾·aj funkci¹·oj.

ĉie⭑·a rekursi⁽⁺⁾·a funkci¹·o, ĈRF

          {μ-rekursia funkci¹·o} kiu est⭑·as {ĉie⭑·a funkci¹·o} : ĉiu {PRF} est⭑·as
          ĉie⭑·a rekursi⁽⁺⁾·a funkci¹·o; ekzist⭑·as ĉie⭑·aj rekursi⁽⁺⁾·aj funkci¹·oj kiu·j ne⭑
          est⭑·as {primitiv²·e rekursi⁽⁺⁾·aj} .

   [artikol⭑-versi⁹·o: 1.8 2023/06/08 22:29:32 ]
     __________________________________________________________________