Predictable order

In theoretical computer science , more precisely in the theory of computability , calculable orders denote certain decidable relations . They form the starting point for semi-calculable quantities as well as for calculable ordinal numbers .

definition

Let it be a total order on the set of natural numbers . ${\displaystyle \leq _{R}\,\subseteq \mathbb {N} \times \mathbb {N} }$

The relation is called ${\displaystyle \leq _{R}}$ computable order if the function is totally computable . ${\displaystyle (x;y)\mapsto {\begin{cases}1,&{\text{falls }}x\leq _{R}y,\\0,&{\text{sonst}}\end{cases}}}$

In other words, a computable order is a two-digit, total, reflexive , transitive , antisymmetric and decidable relation on the natural numbers.

In principle, one could consider calculable orders on a different basic area. However, if this is finite, then every total order is calculable; if it is uncountable , it is not. For countably infinite basic areas, on the other hand, there is always a bijection from the natural numbers, along which the order can be withdrawn. ${\displaystyle \mathbb {N} }$

Examples and counterexamples

• The natural arrangement of is predictable. ${\displaystyle \mathbb {N} }$
• The order is also predictable. ${\displaystyle 1<3<5<\cdots <0<2<4<\cdots }$
• Designate the special holding problem and its complement , then is not calculable. ${\displaystyle K=\{x_{1}<x_{2}<\cdots \}}$ ${\displaystyle {\overline {K}}=\{y_{1}<y_{2}<\cdots \}}$ ${\displaystyle x_{1}<x_{2}<\cdots <y_{1}<y_{2}<\cdots \ }$

These examples show that order isomorphism and predictability are independent of each other. In particular, an order automorphism is only calculable if it is calculable itself.

Semi-computable quantities

A lot of hot ${\displaystyle A\subseteq \mathbb {N} }$ semi-computable (from English semirecursive ), if there is a totally computable function such that and holds. ${\displaystyle f}$ ${\displaystyle \forall x;y\colon f(x;y)\in \{x;y\}}$ ${\displaystyle \forall x;y\colon \{x;y\}\cap A\neq \emptyset \Rightarrow f(x;y)\in A}$

In other words, for every two natural numbers, the one that is closer to in is calculated . This means that as soon as at least one of the two inputs is actually in , an element of is also returned. ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

Note : The concept of the semi-computable set must not be confused with that of the semi-decidable set.

The following characterization now results:

A set is semi-computable if and only if it is an initial part of a computable order. ${\displaystyle A}$

The following properties also apply:

• Decidable sets are semi-computable; the reverse is generally not true.
• Complements of semi-computable sets are also semi-computable again.
• Is many-one reducible to a semi-predictable amount , so is also semi-predictable. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\preceq _{m}B}$ ${\displaystyle A}$
• Every Turing degree contains a semi-calculable set. In fact there is one in every degree, cf. Reduction . ${\displaystyle tt}$
• Simple semi-computable sets are hyper-simple .

literature

• H. Rogers Jr.: Theory of recursive functions and effective computability. 2nd ed., 1987, MIT Press, Cambridge MA, ISBN 0-262-68052-1 .
• P. Odifreddi : Classical Recursion Theory . North-Holland, 1989, ISBN 0-444-87295-7 .