Namespaces
Variants
Actions

Difference between revisions of "Least-number operator"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
''<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577702.png" />-operator, minimization operator''
+
{{TEX|done}}
 +
''$\mu$-operator, minimization operator''
  
A device for constructing new functions out of others, as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577703.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577704.png" />-ary arithmetic function, i.e. a function with arguments and values in the set of natural numbers. It is assumed here that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577705.png" /> is a partial function, i.e. it is not necessarily defined for all values of its arguments. One says that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577706.png" />-ary arithmetic function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577707.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577708.png" /> by the least-number operator if, for any natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l0577709.png" />,
+
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$,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777010.png" /></td> </tr></table>
+
$$f(k_1,\ldots,k_n)=k$$
  
if and only if the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777011.png" /> are defined and are not equal to zero for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777012.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777013.png" /> is defined and equals zero. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777014.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777015.png" /> by the least-number operator, one writes
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777016.png" /></td> </tr></table>
+
$$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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777017.png" /> is a [[Computable function|computable function]], then the above function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777018.png" /> is always partially computable. In fact, if there is an algorithm computing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777019.png" />, then the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777020.png" /> can be computed as follows. Compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777021.png" />. If the computation process ends, i.e. if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777022.png" /> is defined, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777023.png" />, put <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777024.png" />; but if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777025.png" />, begin to compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777026.png" />. If the process ends and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777027.png" />, put <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777028.png" />; but if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777029.png" />, proceed to compute <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777030.png" />; etc. The computation will come to an end if there exists a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777031.png" /> such that, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777033.png" /> is defined and not zero, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777034.png" /> is defined and equal to zero. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057770/l05777035.png" />.
+
An important property of the least-number operator is the following: If $g$ is a [[Computable function|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|Partial recursive function]]).
 
The least-number operator plays an important role in the definition of the class of partial recursive functions (cf. [[Partial recursive function|Partial recursive function]]).

Latest revision as of 07:06, 12 August 2014

$\mu$-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