Predictable operator

Computable operators (also: effective operators ; English: recursive operator , effective operator ) are in theoretical computer science , more precisely in computability theory , manipulations of partial functions that are realized by Turing machines . Computable functionals are assignments of functions to natural numbers mediated by Turing machines . Computable functionals are needed to create computable operatorsto be precisely defined mathematically. In addition to their independent importance in the theory of computability, computable operators form the technical basis of algorithmic learning theory . Computable operators are a special case of enumeration operators .

definition

In the following it denotes the set of all partial mappings of natural numbers, denotes the subset of the total functions . Furthermore, let us assume a computable coding function for finite tuples of natural numbers ( e.g. Cantor's pairing function ). If we identify a function with its graph , then allowed again to regard this as a subset of the natural numbers: . ${\displaystyle {\mathfrak {P}}}$ ${\displaystyle \psi \colon \mathbb {N} \rightsquigarrow \mathbb {N} }$ ${\displaystyle {\mathfrak {R}}}$ ${\displaystyle \langle \cdot \rangle }$ ${\displaystyle \psi \in {\mathfrak {P}}}$ ${\displaystyle \langle \cdot \rangle }$ ${\displaystyle \psi =\{\langle x;\psi (x)\rangle |x\in \operatorname {dom} (\psi )\}\subseteq \mathbb {N} }$

Intuitive version

• An operator hot computable if there is a Turing machine (not necessarily itself predictable) for any bullets of graphene as an input part, the graph of enumerating. ${\displaystyle \Theta \colon {\mathfrak {P}}\to {\mathfrak {P}}}$ ${\displaystyle \psi }$ ${\displaystyle \Theta (\psi )}$
• His name was totally predictable and generally predictable (ger .: total recursive , general recursive ) if it additionally complete functions transferred again to complete functions . ${\displaystyle \Theta ({\mathfrak {R}})\subseteq {\mathfrak {R}}}$

For this definition, the operation of a Turing machine has to be modified slightly: Instead of a single natural number, it now receives successively longer, finite initial parts of the corresponding enumeration of as input. This definition can easily be extended ( e.g. using multiple input bands ) to operators for any arity . ${\displaystyle \psi }$ ${\displaystyle \Theta \colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l}\to {\mathfrak {P}}}$ ${\displaystyle k;l\in \mathbb {N} }$

Formal version

Let there be an effective numbering of all partial functions with a finite domain . For each recursively enumerable set a computable enumeration with image set or fixed. ${\displaystyle \{\sigma _{i}\}_{i\in \mathbb {N} }}$ ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle \nu _{A}\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle \operatorname {im} (\nu _{A})=A}$ ${\displaystyle \nu _{\emptyset }=\bot }$

• A functional hot computable if there is a recursively enumerable set there, so for all partial functions and natural numbers applies: . ${\displaystyle F\colon {\mathfrak {P}}\times \mathbb {N} \rightsquigarrow \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle \psi }$ ${\displaystyle x\in \mathbb {N} }$ ${\displaystyle F(\psi ;x){\downarrow }\Leftrightarrow \exists i;z\colon (\sigma _{i}\subseteq \psi \land \langle i;x;z\rangle \in A)}$

In this case there is such a triple for the first , which is enumerated by. ${\displaystyle F(\psi ;x)=z}$ ${\displaystyle \langle i;x;z\rangle }$ ${\displaystyle \nu _{A}}$

• ${\displaystyle F}$is called totally predictable if it is predictable and for total functions itself total, so . ${\displaystyle \psi \in {\mathfrak {R}}\Rightarrow \forall x\colon F(\psi ;x){\downarrow }}$

The same applies to functionals . ${\displaystyle F\colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l}\rightsquigarrow \mathbb {N} }$

• An operator name is predictable if a predictable functional are such that for any partial functions and natural numbers applies: . ${\displaystyle \Theta \colon {\mathfrak {P}}\to {\mathfrak {P}}}$ ${\displaystyle F\colon {\mathfrak {P}}\times \mathbb {N} \rightsquigarrow \mathbb {N} }$ ${\displaystyle \psi }$ ${\displaystyle x}$ ${\displaystyle \Theta (\psi )(x)=F(\psi ;x)}$
• ${\displaystyle \Theta }$hot totally predictable if the operator maps functions on total total, . ${\displaystyle \psi \in {\mathfrak {R}}\Rightarrow \forall x\colon \Theta (\psi )(x){\downarrow }}$

Similarly, operators are defined by functionals . ${\displaystyle \Theta \colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l}\to {\mathfrak {P}}}$ ${\displaystyle F\colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l+1}\rightsquigarrow \mathbb {N} }$

Explanation

The numbering of the recursively enumerable set takes on the character of a search area . To calculate the corresponding functional , entries on finite restrictions of the function are searched for. If no suitable entry is found, the calculation never terminates and the functionality remains undefined at this point. Fixing the enumerating procedure ensures that it is well defined . ${\displaystyle \sigma _{i}}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle \psi }$ ${\displaystyle \nu _{A}}$ ${\displaystyle F}$

The input function is provided by an external source, which is why neither the function itself nor the selected enumeration needs to be calculable. This can be interpreted in such a way that the Turing machine asks a human user to enter new pairs during the calculation . In other words , the Turing machine learns the input function and transforms it at the same time. The above definition ensures that the result of this manipulation does not depend on the order in which the graph of is presented. ${\displaystyle \psi }$ ${\displaystyle \langle x;\psi (x)\rangle }$ ${\displaystyle \psi }$

While effective operators are always total, this need not apply to the underlying functionals, because there may be non-total functions in the operator's image. It should therefore be noted that there are operators that are total and calculable, but not totally calculable in the sense of the definition. One example is the constant operator that maps every function to the function that is undefined everywhere ; this can be calculated with the choice . ${\displaystyle \bot }$ ${\displaystyle A=\emptyset }$

Examples

• A constant operator is only effective when the objective function can be calculated, e.g. the successor function . ${\displaystyle \Theta ^{c;S}(\psi )=(x\mapsto x+1)}$
• Identity : . ${\displaystyle \Theta ^{I}(\psi )=\psi }$
• Left-Shift : . ${\displaystyle \Theta ^{L}(\psi )(x)=\psi (x+1)}$
• Evaluation on the site : . ${\displaystyle 0}$ ${\displaystyle F^{E}(\psi ;x)=\psi (0)}$

properties

It denotes the class of the computable functions and, analogously, the subset of the totally computable mappings. In addition, let there be an effective numbering of (e.g. the Gödel numbering of all deterministic Turing machines), so the canonical numbering of all recursively enumerable sets is given. ${\displaystyle {\mathcal {P}}\subsetneq {\mathfrak {P}}}$ ${\displaystyle {\mathcal {R}}\subsetneq {\mathfrak {R}}}$ ${\displaystyle \{\varphi _{p}\}_{p\in \mathbb {N} }}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle \forall p\colon W_{p}=\operatorname {dom} (\varphi _{p})}$

From the above definition, some important properties immediately emerge:

• There is an effective numbering of all computable operators, namely through the setting . ${\displaystyle \{\Theta _{p}\}_{p\in \mathbb {N} }}$ ${\displaystyle A=W_{p}}$
• For every computable operator there is a totally computable function , so that . ${\displaystyle f\in {\mathcal {R}}}$ ${\displaystyle \forall p\colon \Theta (\varphi _{p})=\varphi _{f(p)}}$
  • In particular, calculable operators convert calculable functions back into calculable functions , this motivates the name. ${\displaystyle \Theta ({\mathcal {P}})\subseteq {\mathcal {P}}}$
  • The following also applies to generally computable operators . ${\displaystyle \Theta ({\mathcal {R}})\subseteq {\mathcal {R}}}$
• The composition of (generally) calculable operators is again (generally) calculable.
  • There's even a totally predictable function so that . ${\displaystyle g\in {\mathcal {R}}}$ ${\displaystyle \forall p;q\colon \Theta _{g(\langle p;q\rangle )}=\Theta _{p}\circ \Theta _{q}}$

The following applies to computable operators , partial functions and natural numbers : ${\displaystyle \Theta }$ ${\displaystyle \psi }$ ${\displaystyle x}$

• Monotony : . ${\displaystyle \Theta (\psi )(x){\downarrow }\Rightarrow \forall \chi \supseteq \psi \colon \Theta (\chi )(x){\downarrow }=\Theta (\psi )(x)}$
• Compactness : . ${\displaystyle \Theta (\psi )(x){\downarrow }\Rightarrow \exists \sigma \subset _{\text{fin}}\psi \colon \Theta (\sigma )(x){\downarrow }=\Theta (\psi )(x)}$
• Consistency : . ${\displaystyle \textstyle \Theta (\psi )=\bigcup _{\sigma \subset _{\text{fin}}\psi }\Theta (\sigma )}$

Actually, compactness and continuity are two formulations of the same property. The term compactness refers to the compactness theorems of mathematical logic . Continuity, on the other hand, indicates that computable operators are actually continuous as mappings , given the topology generated by the base sets. ${\displaystyle {\mathfrak {P}}}$ ${\displaystyle \{\psi \in {\mathfrak {P}}|\sigma _{i}\subset _{\text{fin}}\psi \}_{i\in \mathbb {N} }}$

Operator recursion set

→ Main article : Recursion theorem

The fundamental theorem about computable operators is John Case's Operator Recursion Theorem :

For each computable operator a total computable function exists strictly increasing , so that: . ${\displaystyle \Theta }$ ${\displaystyle e\in {\mathcal {R}}}$ ${\displaystyle \forall p;x\colon \varphi _{e(p)}(x)=\Theta (e)(p;x)}$

The sentence provides an infinite number of programs of calculable functions, all of which are aware of themselves and of the transformation described. ${\displaystyle e(p)}$ ${\displaystyle \Theta }$

Enumerable reduction

→ Main article : Enumerable reduction

Be partial functions. ${\displaystyle \psi ;\chi \in {\mathfrak {P}}}$

• The figure hot enumerable reducible to (ger .: enumeration reducible to ) or partially computable , if there is a computable operator is so . ${\displaystyle \chi }$ ${\displaystyle \psi }$ ${\displaystyle \chi \preceq _{e}\psi }$ ${\displaystyle \Theta }$ ${\displaystyle \Theta (\psi )=\chi }$

The reduction defines a pre-order on the set , in particular the relation is transitive . The following applies to every two calculable functions , in addition there is no function that is genuinely below the class of calculable mappings. Both can easily be shown using constant operators ( see above ). ${\displaystyle \preceq _{e}}$ ${\displaystyle {\mathfrak {P}}}$ ${\displaystyle f;g\in {\mathcal {P}}}$ ${\displaystyle f\equiv _{e}g}$ ${\displaystyle {\mathfrak {P}}}$ ${\displaystyle \preceq _{e}}$ ${\displaystyle {\mathcal {P}}}$

For totally predictable pictures even that is true if and only predictable in is when the graph of (natural than quantity numbers) Turing reducible to the graph of is . In general, however, the enumerable reduction is incomparable with the Turing reduction. ${\displaystyle f;g\in {\mathcal {R}}}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\preceq _{e}g\Leftrightarrow f\preceq _{T}g}$

swell

• John W. Case: Periodicity in Generations of Automata . In: Springer-Verlag (Ed.): Mathematical Systems Theory . 8, No. 1, 1974, pp. 15-32. doi : 10.1007 / BF01761704 .
• Sharma Jain et al .: Systems That Learn , 2nd. Edition, MIT Press, Cambridge, Massachusetts 1999, ISBN 0-262-10077-0 , p. 19.
• Hartley Rogers, Jr .: Theory of Recursive Functions and Effective Computability . McGraw-Hill, Cambridge, Massachusetts 1987, ISBN 0-262-68052-1 , pp. 145-149.