Primitive recursive function: Difference between revisions

Revision as of 19:08, 10 June 2025

Revision as of 22:49, 13 June 2025

Line 26:

| 4=''Composition operator'' <math>\circ\,</math> (also called the ''substitution operator''): Given an ''m''-ary function <math>h(x_1,\ldots,x_m)\,</math> and ''m'' ''k''-ary functions <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>: <math display="block">h \circ (g_1, \ldots, g_m) \ \stackrel{\mathrm{def}}{=}\ f, \quad\text{where}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)).</math> For <math>m=1</math>, the ordinary [[function composition]] <math>h \circ g_1</math> is obtained.

| 5=''Primitive recursion operator'' <math>\rho</math>: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and the <math>(''k''&nbsp;+&nbsp;2)</math>-ary function <math>h(y,z,x_1,\ldots,x_k)\,</math>:
:<math display="block">\begin{align}

\rho(g, h) &\ \stackrel{\mathrm{def}}{=}\ f, \quad\text{where the }(k+1)\text{-ary function } f \text{ is defined by}\\

f(0y, x_1, \ldotsdots, x_k) &= g(x_1,\ldots,x_k) \\begin{cases}

g(x_1, \dots, x_k) & \text{if } y=0 \\

f(S(y),x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k).\end{align}</math>

h(y', f(x_1, \dots, x_k) ,x_1, \dots, x_k) & \text{if } y=S(y') \text{ for a } y' \in \mathbb{N} \\

\end{cases}

\end{align}</math>

''Interpretation:''

The function <math>f</math> acts as a [[for loop|for-loop]] from <math>0</math> up to the value of its first argument. The rest of the arguments for <math>f</math>, denoted here with <math>x_1,\ldots,x_k</math>, are a set of initial conditions for the for-loop which may be used by it during calculations but which are immutable by it. The functions <math>g</math> and <math>h</math> on the right-hand side of the equations that define <math>f</math> represent the body of the loop, which performs calculations. The function <math>g</math> is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed by <math>h</math>. The first parameter of <math>h</math> is fed the "current" value of the for-loop's index. The second parameter of <math>h</math> is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters for <math>h</math> are those immutable initial conditions for the for-loop mentioned earlier. They may be used by <math>h</math> to perform calculations but they will not themselves be altered by <math>h</math>.