Definition:Enumeration Operator (Recursion Theory)
Jump to navigation
Jump to search
This page is about Enumeration Operator in the context of Recursion Theory. For other uses, see Enumeration Operator.
Definition
Let $\phi \subseteq \N$ be recursively enumerable.
Let $\pi : \N^2 \to \N$ be the Cantor pairing function.
- Then, $\map \pi {x, y}$ codes the pair $\tuple {x, y}$.
Define the mapping $\psi : \powerset \N \to \powerset \N$ as:
- $\map \psi A = \set {x \in \N : \exists \text { finite } B \subseteq A : \map \pi {x, b} \in \phi}$
where $b \in \N$ is the code number for $B$.
Then $\psi$ is an enumeration operator.
Also see
Sources
- 1967: Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability
- Enumeration operator. Encyclopedia of Mathematics. URL: https://www.encyclopediaofmath.org/index.php?title=Enumeration_operator&oldid=46831