Namespaces
Variants
Actions

Least-number operator

From Encyclopedia of Mathematics
Jump to: navigation, search

-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
How to Cite This Entry:
Least-number operator. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Least-number_operator&oldid=32848
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article