Content deleted Content added
m →Examples: \operatorname |
m →Examples: Adding wikilink |
||
Line 49:
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 {{mvar|x}} can be defined as the least {{mvar|z}} such that <math>(z+1)^2 > x</math>. Using the minimization operator, a general recursive definition is <math>\operatorname{Isqrt} = \mu(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{Mul} \circ (S \circ P_1^2,S \circ P_1^2), P_2^2))</math>, where {{math|Not}}, {{math|Gt}}, and {{math|Mul}} are [[logical negation]], greater-than, and multiplication,<ref>defined in [[Primitive recursive function#Junctors]], [[Primitive recursive function#Equality predicate]], and [[Primitive recursive function#Multiplication]]</ref> respectively. In fact, <math>(\operatorname{Not} \circ \operatorname{Gt} \circ (\operatorname{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 {{
}}
The following examples define general recursive functions that are not primitive recursive; hence they cannot avoid using the minimization operator.
| |||