Vorto: PRF

  1. La difino estas rikura: 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](x1,…xn)=xm, 1≤m≤n. La operatoroj estas la kunligo 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

    • ĉiuj primitive rekursiaj funkcioj estas ĉieaj funkcioj

    • pliopo da nombroteoriaj funkcioj estas primitive rekursiaj funkcioj

En aliaj lingvoj

    • La angla: primitive recursive function
    • La rusa: примитивно-рекурсивная функция