Enumeration operator

Enumeration operators (ger .: enumeration operator ) are in theoretical computer science , more precisely in the computability theory , certain predictable mappings between sets of natural numbers . They are thus a generalization of computable operators . Enumeration operators define a reduction between the sets involved.

definition

Enumeration operator

Let there be an effective numbering of all finite subsets of (e.g. for ). Next is a computable coding function for pairs of natural numbers. ${\displaystyle \{D_{i}\}_{i\in \mathbb {N} }}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle D_{i}=\{x_{1};x_{2};\dots ;x_{n}\}}$ ${\displaystyle i=2^{x_{1}}+2^{x_{2}}+\dots +2^{x_{n}}}$ ${\displaystyle \langle \cdot ;\cdot \rangle \colon \mathbb {N} ^{2}\to \mathbb {N} }$

• A picture between subsets of natural numbers hot list operator if there is a recursively enumerable set is such that for any amount applies: . ${\displaystyle \Psi \colon {\mathcal {P}}(\mathbb {N} )\to {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle S\subseteq \mathbb {N} }$ ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle x\in \Psi (A)\Leftrightarrow \exists i\colon (D_{i}\subseteq A\land \langle i;x\rangle \in S)}$

Enumeration operators can evidently be implemented by Turing machines : The corresponding machine receives ever larger, finite subsets of as input from an external source - for example a human user . At the same time, it searches the search area for suitable entries ; if one is found, the output is . Little by little the entire amount is enumerated. ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle \langle i;x\rangle }$ ${\displaystyle x}$ ${\displaystyle \Psi (A)}$

Enumerable reduction

• A lot of hot enumerable reducible to (ger .: enumeration reducible ), if there is a list operator is so true. ${\displaystyle B\subseteq \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle B\preceq _{e}A}$ ${\displaystyle \Psi }$ ${\displaystyle \Psi (A)=B}$

If an enumeration of the set is given (be it calculable or not), the operator also conveys an enumeration of (cf. Reduction (Theoretical Computer Science) ). It follows that the set is recursively enumerable in (cf. Oracle-Turing machine ), the converse generally does not hold. Enumeration operators therefore always map recursively enumerable sets to recursively enumerable sets, this motivates the designation. ${\displaystyle A}$ ${\displaystyle \Psi }$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

Examples

There are some trivial enumeration operators, for example identity or left shift . Constant operators are enumeration operators if and only if the target set can be enumerated recursively, such as for the special holding problem . Other predictable manipulations of the input quantities can be mediated by enumeration operators . ${\displaystyle \Psi ^{I}(A)=A}$ ${\displaystyle \Psi ^{L}(A)=\{a+1|a\in A\}}$ ${\displaystyle \Psi ^{c;K}(A)=K}$ ${\displaystyle K}$ ${\displaystyle \Psi ^{\pi _{2}}(A)=\{y|\exists x\colon \langle x;y\rangle \in A\}}$

The actual intention of the above definition is to create a calculable analogue to inductive definitions . For example, a set of inductive equations could be as follows (see Fibonacci sequence ):

${\displaystyle f(0)=0;}$

${\displaystyle f(1)=1;}$

${\displaystyle f(n+2)=f(n)+f(n+1).}$

This can be reformulated into an enumeration operator for the graphs of possible solutions by explicitly specifying the underlying search space . For better readability, the finite sets are used here instead of their code numbers . In addition, the elements of the target set are interpreted as encoded pairs of natural numbers. Necessarily then contains the elements and , since every solution has to map the and that to itself on the basis of the first two equations . Furthermore, for any natural numbers, contain the pair . This realizes the third equation, because if the information is now known from the input quantity that applies to the targeted solution and , then it also applies to the output quantity. ${\displaystyle \Psi _{f}}$ ${\displaystyle f}$ ${\displaystyle S}$ ${\displaystyle D_{i}}$ ${\displaystyle i}$ ${\displaystyle S}$ ${\displaystyle \langle \emptyset ;(0;0)\rangle }$ ${\displaystyle \langle \emptyset ;(1;1)\rangle }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle S}$ ${\displaystyle n;m;k\in \mathbb {N} }$ ${\displaystyle \langle \{(n;m);(n+1;k)\};(n+2;m+k)\rangle }$ ${\displaystyle n\mapsto m}$ ${\displaystyle n+1\mapsto k}$ ${\displaystyle \Psi _{f}}$ ${\displaystyle n+2\mapsto m+k}$

properties

• There is an effective numbering of all enumeration operators, this results immediately from the canonical numbering of all recursively enumerable sets. ${\displaystyle \{\Psi _{p}\}_{p\in \mathbb {N} }}$

For an enumeration operator , sets and natural numbers : ${\displaystyle \Psi }$ ${\displaystyle A;B\subseteq \mathbb {N} }$ ${\displaystyle x}$

• Monotony : . ${\displaystyle A\subseteq B\Rightarrow \Psi (A)\subseteq \Psi (B)}$
• Compactness : . ${\displaystyle x\in \Psi (A)\Rightarrow \exists D\subset _{\text{fin}}A\colon x\in \Psi (D)}$

It also follows from compactness that enumeration operators are continuous as mappings if the power set is given the topology that is generated by the base sets. ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle \{A\subseteq \mathbb {N} |D_{i}\subset _{\text{fin}}A\}_{i\in \mathbb {N} }}$

• There is a totally predictable function such that . ${\displaystyle g}$ ${\displaystyle \forall p;q\colon \Psi _{g(\langle p;q\rangle )}=\Psi _{p}\circ \Psi _{q}}$
  • In particular, the class of enumeration operators is closed under composition .
• Like all reductions , a preorder is on , the relation in particular is transitive . ${\displaystyle \preceq _{e}}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$
• The Truth-table-reduction (and therefore also the many-one reduction ) implies the enumerable reduction . ${\displaystyle B\preceq _{1}A\Rightarrow B\preceq _{m}A\Rightarrow B\preceq _{tt}A\Rightarrow B\preceq _{e}A}$

The implications are strict in each case.

• The enumerable reduction and the Turing reduction , on the other hand, are incomparable.

Computable operators

→ Main article : Computable operator

A lot of natural numbers name is quite clear , if the following applies: . Let it denote the set of all partial mappings of natural numbers. If you identify a function with its graph , this allows you to understand it as a subset of the natural numbers. This explains an embedding . Your picture consists of the right-unambiguous sets. ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle \langle x;y\rangle ;\langle x;z\rangle \in A\Rightarrow y=z}$ ${\displaystyle {\mathfrak {P}}}$ ${\displaystyle \psi \colon \mathbb {N} \rightsquigarrow \mathbb {N} }$ ${\displaystyle \psi \in {\mathfrak {P}}}$ ${\displaystyle \langle \cdot ;\cdot \rangle }$ ${\displaystyle {\mathfrak {P}}\hookrightarrow {\mathcal {P}}(\mathbb {N} );\ \psi \mapsto \{\langle x;\psi (x)\rangle |x\in \operatorname {dom} (\psi )\}}$

If now applies to an enumeration operator , i.e. if it converts right-unambiguous sets back into right-unambiguous sets, the restriction is a computable operator . In this way all computable operators are obtained. It is then necessary to map calculable functions back to calculable ones. ${\displaystyle \Psi ({\mathfrak {P}})\subseteq {\mathfrak {P}}}$ ${\displaystyle \Psi |_{\mathfrak {P}}}$ ${\displaystyle \Psi }$

Recursion sentence

→ Main article : Recursion theorem

There is a recursion theorem for enumeration operators. This is weaker than the corresponding sentence for computable operators, which is why it is sometimes referred to as weak recursion theorem in English literature .

• For each Aufzählungsorperator there is a recursively enumerable set such that a fixed point is, and each fixed point of the set contains. ${\displaystyle \Psi }$ ${\displaystyle F\subseteq \mathbb {N} }$ ${\displaystyle F}$ ${\displaystyle \Psi (F)=F}$ ${\displaystyle \Psi }$ ${\displaystyle F}$
• If it is even a computable operator, there is a partially computable function , so that and every right-unambiguous fixed point of has the function as a restriction. ${\displaystyle \Psi |_{\mathfrak {P}}}$ ${\displaystyle \psi }$ ${\displaystyle \Psi (\psi )=\psi }$ ${\displaystyle \Psi }$ ${\displaystyle \psi }$

The fixed point can even be stated explicitly: Let be and for every natural number be , then is . The second part now follows from the first through the observation that in this case the set is right unambiguous. ${\displaystyle F}$ ${\displaystyle F_{0}=\emptyset }$ ${\displaystyle k}$ ${\displaystyle F_{k+1}=F_{k}\cup \Psi (F_{k})}$ ${\displaystyle \textstyle F=\bigcup _{k}F_{k}}$ ${\displaystyle F}$

For example , if one considers the operator defined above , the smallest fixed point is the graph of the Fibonacci function clearly defined by the equations . Another fixed point, though no longer unambiguous to the right, is the set , since it also satisfies the above equations. The fixed point obviously contains the graph of as a subset. ${\displaystyle \Psi _{f}}$ ${\displaystyle \operatorname {fib} }$ ${\displaystyle \{\langle x;y\rangle |y\leq \operatorname {fib} (x)\}}$ ${\displaystyle \operatorname {fib} }$

swell

• Sharma Jain et al .: Systems That Learn , 2nd. Edition, MIT Press, Cambridge, Massachusetts 1999, ISBN 0-262-10077-0 , p. 19.
• Stephen C. Kleene : Introduction to Metamathematics . North-Holland Publishing Company, New York City, New York 1952, pp. 352-353.
• Hartley Rogers, Jr .: Theory of Recursive Functions and Effective Computability . McGraw-Hill, Cambridge, Massachusetts 1987, ISBN 0-262-68052-1 , pp. 145-149.