View source for Partial recursive operator

A mapping from the class of all one-place functions into itself, defined as follows. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717001.png" /> be some [[Enumeration operator|enumeration operator]]. To this operator one naturally associates another operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717002.png" />, acting on one-place functions. More precisely, each function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717003.png" /> has a graph — the set of all pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717004.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717005.png" />. Given a fixed coding method of pairs of natural numbers, this graph can be treated as a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717006.png" /> of natural numbers. If now <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717007.png" /> is also the graph of some function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717008.png" />, then one puts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p0717009.png" />. Otherwise <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p07170010.png" /> is not defined. Thus, to each enumeration operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p07170011.png" /> one associates a partial recursive operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071700/p07170012.png" />.

If a partial recursive operator is defined on all functions, then it is called a recursive operator. A partial recursive operator that is defined on all everywhere-defined functions and that maps everywhere-defined functions to everywhere-defined functions is called a general recursive operator. Not every partial recursive operator can be extended to a recursive operator. Every general recursive operator is a recursive operator. The converse does not hold.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Rogers jr.,   "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)</TD></TR></table>



====Comments====
Cf. also [[Recursive function|Recursive function]]; [[Computable function|Computable function]].