General recursive function: Difference between revisions

Revision as of 08:19, 13 November 2021

Revision as of 08:23, 13 November 2021

Line 13:

Primitive or "basic" functions:

#'''Constant functions {{mvar|C{{su|b=n|p=k}}}}''': For each natural number <math>{{mvar|n\,</math>}} and every <math>{{mvar|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''' {{mvar|&rho;}}: 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''' {{mvar|&mu;}}: 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

\end{align}</math>

\end{align}</math><br />Intuitively, minimisation seeks—beginning the search from 0 and proceeding upwards—the smallest argument that causes the function to return zero; if there is no such argument, or if one encounters an argument for which {{mvar|f}} is not defined, then the search never terminates, and <math> \mu(f)</math> is not defined for the argument <math>(x_1, \ldots, x_k).</math> <br> (''Note'': While some textbooks use the μ-operator as defined here,<ref name="Enderton.1972">Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972</ref><ref name="Boolos.Burgess.Jeffrey.2007">Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge University Press, 2007</ref> others like<ref name="Jones.1997">Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997</ref><ref>Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, New York, 1982</ref> demand that the μ-operator is applied to ''total'' functions <math>{{mvar|f</math>}} only. Although this restricts the μ-operator as compared to the definition given here, the class of μ-recursive functions remains the same, which follows from Kleene's Normal Form Theorem (see [[#Normal form theorem|below]]).<ref name="Enderton.1972"/><ref name="Boolos.Burgess.Jeffrey.2007"/> The only difference is, that it becomes undecidable whether a specific function definition defines a μ-recursive function, as it is undecidable whether a computable (i.e. μ-recursive) function is total.<ref name="Jones.1997"/>)

The '''strong equality''' operator <math>\simeq</math> can be used to compare partial μ-recursive functions. This is defined for all partial functions ''f'' and ''g'' so that