General recursive function: Difference between revisions

Revision as of 21:33, 23 November 2021

Revision as of 21:41, 23 November 2021

Line 48:

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.

{{unordered list

|The [[integer square root]] of <math>x</math> can be defined as the least <math>z</math> such that <math>(z+1)^2 > x</math>. Using the minimization operator, a general recursive definition is <math>Isqrt = \mu(Not \circ Gt \circ (Mul \circ (S \circ P_1^2,S \circ P_1^2), P_2^2))</math>, where <math>Not</math>, <math>Gt</math>, and <math>Mul</math> are logical negation, greater-than, and multiplication,<ref>defined in [[Primitive recursive function#Junctors]], [[Primitive recursive function#PredicateEquality "Greater or equal"predicate]], and [[Primitive recursive function#Multiplication]]</ref> respectively. In fact, <math>(Not \circ Gt \circ (Mul \circ (S \circ P_1^2,S \circ P_1^2), P_2^2)) \; (z,x) = (\lnot S(z)*S(z) > x)</math> is <math>0</math> if, and only if, <math>S(z)*S(z) > x</math> holds. Hence <math>Isqrt(x)</math> is the least <math>z</math> such that <math>S(z)*S(z) > x</math> holds.

}}

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