Namespaces
Variants
Actions

Difference between revisions of "Partial recursive operator"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
 
Line 1: Line 1:
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" />.
+
A mapping from the class of all one-place functions into itself, defined as follows. Let $\Phi_z$ be an [[enumeration operator]]. To this operator one naturally associates another operator $\Psi$, acting on one-place functions. More precisely, each function $\phi$ has a graph — the set of all pairs $(x,y)$ such that $\phi(x) = y$. Given a fixed coding method of pairs of natural numbers, this graph can be treated as a set $\tau(\phi)$ of natural numbers. If now $\Phi_z(\tau(\phi))$ is also the graph of some function $\psi$, then one puts $\Psi(\phi) = \psi$. Otherwise $\Psi(\phi)$ is not defined. Thus, to each enumeration operator $\Phi_z$ one associates a partial recursive operator $\Psi$.
  
 
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.
 
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====
 
====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>
+
<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]]; [[Computable function]].
  
====Comments====
+
{{TEX|done}}
Cf. also [[Recursive function|Recursive function]]; [[Computable function|Computable function]].
 

Latest revision as of 18:27, 3 September 2017

A mapping from the class of all one-place functions into itself, defined as follows. Let $\Phi_z$ be an enumeration operator. To this operator one naturally associates another operator $\Psi$, acting on one-place functions. More precisely, each function $\phi$ has a graph — the set of all pairs $(x,y)$ such that $\phi(x) = y$. Given a fixed coding method of pairs of natural numbers, this graph can be treated as a set $\tau(\phi)$ of natural numbers. If now $\Phi_z(\tau(\phi))$ is also the graph of some function $\psi$, then one puts $\Psi(\phi) = \psi$. Otherwise $\Psi(\phi)$ is not defined. Thus, to each enumeration operator $\Phi_z$ one associates a partial recursive operator $\Psi$.

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

[1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)


Comments

Cf. also Recursive function; Computable function.

How to Cite This Entry:
Partial recursive operator. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Partial_recursive_operator&oldid=41806
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article