Partial recursive operator

From Encyclopedia of Mathematics
Revision as of 17:18, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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.


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


Cf. also Recursive function; Computable function.

How to Cite This Entry:
Partial recursive operator. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article