Least-number operator
-operator, minimization operator
A device for constructing new functions out of others, as follows. Let g be an (n+1)-ary arithmetic function, i.e. a function with arguments and values in the set of natural numbers. It is assumed here that g is a partial function, i.e. it is not necessarily defined for all values of its arguments. One says that the n-ary arithmetic function f is obtained from g by the least-number operator if, for any natural numbers k_1,\ldots,k_n,k,
f(k_1,\ldots,k_n)=k
if and only if the values of g(k_1,\ldots,k_n,l) are defined and are not equal to zero for all l<k, while g(k_1,\ldots,k_n,k) is defined and equals zero. If f is obtained from g by the least-number operator, one writes
f(x_1,\ldots,x_n)=\mu y[g(x_1,\ldots,x_n,y)=0].
An important property of the least-number operator is the following: If g is a computable function, then the above function f is always partially computable. In fact, if there is an algorithm computing g, then the value of f(x_1,\ldots,x_n) can be computed as follows. Compute g(x_1,\ldots,x_n,0). If the computation process ends, i.e. if g(x_1,\ldots,x_n,0) is defined, and if g(x_1,\ldots,x_n,0)=0, put f(x_1,\ldots,x_n)=0; but if g(x_1,\ldots,x_n,0)\neq0, begin to compute g(x_1,\ldots,x_n,1). If the process ends and g(x_1,\ldots,x_n,1)=0, put f(x_1,\ldots,x_n)=1; but if g(x_1,\ldots,x_n,1)\neq0, proceed to compute g(x_1,\ldots,x_n,2); etc. The computation will come to an end if there exists a y such that, for all z<y, g(x_1,\ldots,x_n,z) is defined and not zero, while g(x_1,\ldots,x_n,y) is defined and equal to zero. Then f(x_1,\ldots,x_n)=y.
The least-number operator plays an important role in the definition of the class of partial recursive functions (cf. Partial recursive function).
Comments
References
[a1] | H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165 |
Least-number operator. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Least-number_operator&oldid=32848