Primitive recursive function: Difference between revisions

Revision as of 00:23, 18 May 2024

Revision as of 08:30, 23 June 2024

Line 13:

{{ordered list|start=1

|1=''Constant functions {{mvar|C{{su|b=n|p=<math>C_n^k}}}}</math>'': For each natural number {{mvar|<math>n}}</math> and every {{mvar|<math>k}}</math>, the ''k''-ary constant function, defined by <math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n</math>, is primitive recursive.

| 2=''Successor function'': The 1-ary successor function ''S'', which returns the successor of its argument (see [[Peano postulates]]), that is, <math>S(x) \ \stackrel{\mathrm{def}}{=}\ x + 1</math>, is primitive recursive.

Line 21:

{{ordered list|start=4

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

| 5=''Primitive recursion operator'' {{mvar|&<math>\rho;}}</math>: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and the (''k''&nbsp;+&nbsp;2)-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(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\