Namespaces
Variants
Actions

Partial recursive operator

From Encyclopedia of Mathematics
Jump to: navigation, search

A mapping from the class of all one-place functions into itself, defined as follows. Let 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