General recursive function: Difference between revisions

Revision as of 03:09, 17 October 2021

Revision as of 08:19, 13 November 2021

Line 13:

Primitive or "basic" functions:

#'''Constant functions C{{su|b=n|p=k}}''': For each natural number <math>n\,</math> and every <math>k\,</math><br />&nbsp;&nbsp;&nbsp;&nbsp;<math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n</math><br />Alternative definitions use instead a '''zero function''' as a primitive function that always returns zero, and built the constant functions from the zero function, the successor function and the composition operator.

# '''Successor function S:'''<br />&nbsp;&nbsp;&nbsp;&nbsp;<math>S(x) \ \stackrel{\mathrm{def}}{=}\ x + 1\,</math>

# '''Projection function''' <math>P_i^k</math> (also called the '''Identity function'''): For all natural numbers <math>i, k</math> such that <math>1\le i\le k</math>:<br />&nbsp;&nbsp;&nbsp;&nbsp;<math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ x_i \, .</math>

Operators (the [[___domain of a function]] defined by an operator is the set of the values of the arguments such that every function application that must be done during the computation provides a well-defined result):

# '''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>:<br />&nbsp;&nbsp;&nbsp;&nbsp;<math>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><br />This means that <math>f(x_1,\ldots,x_k)</math> is defined only if <math>g_1(x_1,\ldots,x_k),\ldots, g_m(x_1,\ldots,x_k),</math> and <math>h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k))</math> are all defined.

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

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

f(0,x_1,\ldots,x_k) &= g(x_1,\ldots,x_k) \\

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><br />This means that <math>f(y,x_1,\ldots,x_k)</math> is defined only if <math>g(x_1,\ldots,x_k)</math> and <math>h(z,f(z,x_1,\ldots,x_k),x_1,\ldots,x_k)</math> are defined for all <math>z<y.</math>

#'''Minimization operator''' <math>\ {{mvar|&mu\,</math>;}}: Given a (''k''+1)-ary function <math>f(y, x_1, \ldots, x_k)\,</math>, the ''k''-ary function <math>\mu(f)</math> is defined by:<br />&nbsp;&nbsp;&nbsp;&nbsp;<math>\begin{align}

\mu(f)(x_1, \ldots, x_k) = z \stackrel{\mathrm{def}}{\iff}\ f(i, x_1, \ldots, x_k)&>0 \quad \text{for}\quad i=0, \ldots, z-1 \quad\text{and}\\

f(z, x_1, \ldots, x_k)&=0\quad