## Quick Reference

**operator**. The functions involved are usually over the natural numbers. Let *g* be a function of

*n*+1

variables. Then, for any given values of *x*_{1},…,*x** _{n}*, the expression μ

*y*.

*g*(

*x*

_{1},…,

*x*

*,*

_{n}*y*)is evaluated by searching for the smallest value of

*y*for which

*g*(

*x*

_{1},…,

*x*

*,*

_{n}*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*(

*x*

_{1},…,

*x*

*,*

_{n}*y*)is itself undefined; in this case again the μ-expression is undefined.

μ*y*. *g*(*x*_{1},…,*x** _{n}*,

*y*)

*g*(*x*_{1},…,*x** _{n}*,

*y*) = 0

*g*(*x*_{1},…,*x** _{n}*,

*y*)

This construct is used to define a function *f* of *n* variables from the function *g* of *n*+1 variables:*f*(*x*_{1},…,*x** _{n}*) = μ

*y*.

*g*(

*x*

_{1},…,

*x*

*,*

_{n}*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*(*x*_{1},…,*x** _{n}*) = μ

*y*.

*g*(

*x*

_{1},…,

*x*

*,*

_{n}*y*)

**From:**
minimization
in
A Dictionary of Computing »

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.