Partial recursive operator

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.