General recursive function

Examples

Examples not involving the minimization operator can be found at Primitive recursive function#Examples.

The following examples are intended just to demonstrate the use of the minimization operator; they could also be defined without it, albeit in a more complicated way, since they are all primitive recursive.

• The integer square root of x can be defined as the least z such that ${\displaystyle (z+1{)}^2>x}$. Using the minimization operator, a general recursive definition is ${\displaystyle \mathrm{Isqrt}=\mu (\mathrm{Not}\circ \mathrm{Gt}\circ (\mathrm{Mul}\circ (S\circ P_1^2,S\circ P_1^2),P_2^2))}$, where Not, Gt, and Mul are logical negation, greater-than, and multiplication, respectively. In fact, ${\displaystyle (\mathrm{Not}\circ \mathrm{Gt}\circ (\mathrm{Mul}\circ (S\circ P_1^2,S\circ P_1^2),P_2^2))(z,x)=(\mathrm{\neg }S(z)\ast S(z)>x)}$ is 0 if, and only if, ${\displaystyle S(z)\ast S(z)>x}$ holds. Hence ${\displaystyle \mathrm{Isqrt}(x)}$ is the least z such that ${\displaystyle S(z)\ast S(z)>x}$ holds. The negation junctor Not is needed since Gt encodes truth by 1, while μ seeks for 0.

The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.

• Ackermann function

Total recursive function

A general recursive function is called total recursive function if it is defined for every input, or, equivalently, if it can be computed by a total Turing machine. There is no way to computably tell if a given general recursive function is total—see Halting problem.

Equivalence with other models of computability

In the equivalence of models of computability, a parallel is drawn between Turing machines that do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).

Normal form theorem

A normal form theorem due to Kleene says that for each k there are primitive recursive functions ${\displaystyle U(y)}$ and ${\displaystyle T(y,e,x_1,\dots ,x_k)}$ such that for any μ-recursive function ${\displaystyle f(x_1,\dots ,x_k)}$ with k free variables there is an e such that

${\displaystyle f(x_1,\dots ,x_k)\simeq U(\mu (T)(e,x_1,\dots ,x_k))}$.

The number e is called an index or Gödel number for the function f. A consequence of this result is that any μ-recursive function can be defined using a single instance of the μ operator applied to a (total) primitive recursive function.

Minsky observes the ${\displaystyle U}$ defined above is in essence the μ-recursive equivalent of the universal Turing machine:

To construct U is to write down the definition of a general-recursive function U(n, x) that correctly interprets the number n and computes the appropriate function of x. to construct U directly would involve essentially the same amount of effort, and essentially the same ideas, as we have invested in constructing the universal Turing machine

Symbolism

A number of different symbolisms are used in the literature. An advantage to using the symbolism is a derivation of a function by "nesting" of the operators one inside the other is easier to write in a compact form. In the following the string of parameters ${\displaystyle x_1,x_2,\dots ,x_n}$ is abbreviated as ${\displaystyle x}$:

• Constant function: Kleene uses "${\displaystyle C_q^n(x)=q}$" and Boolos-Burgess-Jeffrey (2002) (B-B-J) use the abbreviation "${\displaystyle {\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}}^n(x)=n}$":

e.g. ${\displaystyle C_{13}^7(r,s,t,u,v,w,x)=13}$

e.g. ${\displaystyle {\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}}^{13}(r,s,t,u,v,w,x)=13}$

• Successor function: Kleene uses ${\displaystyle x^{\prime }}$ and ${\displaystyle S}$ for "Successor". As "successor" is considered to be primitive, most texts use the apostrophe as follows:

${\displaystyle S(a)=a+1;\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=};a^{\prime }}$, where

${\displaystyle 1\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{0}^{\prime }}$,

${\displaystyle 2\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}{0}^{″}}$, etc.

• Identity function: Kleene (1952) uses ${\displaystyle U_i^n}$ to indicate the identity function over the variables ${\displaystyle x_i}$; B-B-J use the identity function ${\displaystyle {\mathrm{i}\mathrm{d}}_i^n}$ over the variables ${\displaystyle x_1}$ to ${\displaystyle x_n}$:

${\displaystyle U_i^n(x)={\mathrm{i}\mathrm{d}}_i^n(x)=x_i}$

e.g. ${\displaystyle U_3^7(r,s,t,u,v,w,x)={\mathrm{i}\mathrm{d}}_3^7(r,s,t,u,v,w,x)=t}$

• Composition (Substitution) operator: Kleene uses a bold-face ${\displaystyle {\mathbf{S}}_m^n}$ (not to be confused with his ${\displaystyle S}$ for "successor"!). The superscript ${\displaystyle m}$ refers to the ${\displaystyle m^{th}}$ function ${\displaystyle f_m}$, whereas the subscript ${\displaystyle n}$ refers to the ${\displaystyle n^{th}}$ variable ${\displaystyle x_n}$:

If we are given

${\displaystyle h(x)=g(f_1(x),\dots ,f_m(x))}$

then

${\displaystyle h(x)={\mathbf{S}}_m^n(g,f_1,\dots ,f_m)}$

In a similar manner, but without the sub- and superscripts, B-B-J write:

${\displaystyle h(x^{\prime })=Cg,f_1,\dots ,f_m}$

• Primitive Recursion: Kleene uses the symbol ${\displaystyle R^n(\text{base step},\text{induction step})}$ where n indicates the number of variables; B-B-J use ${\displaystyle Pr(\text{base step},\text{induction step})(x)}$. Given:

• base step: ${\displaystyle h(0,x)=f(x)}$
• induction step: ${\displaystyle h(y+1,x)=g(y,h(y,x),x)}$

Example: primitive recursion definition of ${\displaystyle a+b}$

• base step: ${\displaystyle f(0,a)=a=U_1^1(a)}$U¹
  ₁(a)
• induction step:${\displaystyle f(b^{\prime },a)=(f(b,a){)}^{\prime }=g(b,f(b,a),a)=g(b,c,a)=c^{\prime }=S(U_2^3(b,c,a))}$

${\displaystyle R^2\left(U_1^1(a),;S(U_2^3(b,c,a))\right)}$

${\displaystyle Pr\left(U_1^1(a),;S(U_2^3(b,c,a))\right)}$

Example: Kleene gives an example of how to perform the recursive derivation of ${\displaystyle f(b,a)=b+a}$ (notice reversal of variables ${\displaystyle a}$ and ${\displaystyle b}$). He starts with ${\displaystyle 3}$ initial functions

1. ${\displaystyle S(a)=a^{\prime }}$
2. ${\displaystyle U_1^1(a)=a}$
3. ${\displaystyle U_2^3(b,c,a)=c}$
4. ${\displaystyle g(b,c,a)=S(U_2^3(b,c,a))=c^{\prime }}$
5. base step: ${\displaystyle h(0,a)=U_1^1(a)}$

induction step: ${\displaystyle h(b^{\prime },a)=g(b,h(b,a),a)}$

He arrives at:

${\displaystyle a+b=R^2\left(U_1^1,;S_1^3(S,U_2^3)\right)}$

Examples

• Fibonacci number
• McCarthy 91 function