Content deleted Content added
→Definition: rm "Note"; put note in own paragraph; start Examples section |
→Examples: give a 1st simple example of \mu; prepare for more examples, including properly general recursive ones |
||
Line 45:
===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.
{{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#Predicate "Greater or equal"]], 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.
{{unordered list
|{{example needed}}
}}
== Total recursive function ==
| |||