variables. Then, for any given values of x1,…,xn, the expression μy. g(x1,…,xn,y)is evaluated by searching for the smallest value of y for which g(x1,…,xn,y) = 0 This can be done by letting y run through all natural numbers, in increasing order, until a suitable y is found, whereupon that value of y is returned as the value of the μ-expression. If no suitable y exists the μ-expression is undefined. Also it may happen that before a suitable y is found a value of y is encountered for which g(x1,…,xn,y)is itself undefined; in this case again the μ-expression is undefined.
g(x1,…,xn,y) = 0
This construct is used to define a function f of n variables from the function g of n+1 variables:f(x1,…,xn) = μy. g(x1,…,xn,y) Because of the possibility of the μ-expression being undefined, f is a partial function. The process of searching for values, and the use of minimization, are essential factors that allow the formalism of recursive functions to define all the computable functions.
f(x1,…,xn) = μy. g(x1,…,xn,y)