Retraceable crowd

A set of natural numbers is retraceable (ger .: traceable ) when the next smallest element to each element of the set is calculated can be. Retraceable sets occur in theoretical computer science , more precisely in computability theory , when investigating decidable sets. The theory of retraceable sets goes back to the work of Dekker and Myhill.

Explanation

motivation

For decidable sets the following two functions are and always predictable : ${\displaystyle A=\{a_{0}<a_{1}<a_{2}<\dots \}\subseteq \mathbb {N} }$ ${\displaystyle f}$ ${\displaystyle g}$

1. For everyone , unless it is finite and then applies . ${\displaystyle n}$ ${\displaystyle f(a_{n})=a_{n+1}}$ ${\displaystyle A}$ ${\displaystyle a_{n}=\max A}$ ${\displaystyle f(a_{n})=a_{n}}$
2. For everyone be as well . ${\displaystyle n}$ ${\displaystyle g(a_{n+1})=a_{n}}$ ${\displaystyle g(a_{0})=a_{0}}$

Outside of , the functions can show any behavior. Now the function defined in 1. is calculable if and only if it is decidable. The question therefore arises whether a similar characterization is also possible for those quantities for which it is calculable. These are just the most retraceable amounts. ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle g}$

definition

A set of natural numbers is called retraceable if there is a partially computable function such that . The mapping is then called the retraceable function . ${\displaystyle A=\{a_{0}<a_{1}<a_{2}<\dots \}\subseteq \mathbb {N} }$ ${\displaystyle g\colon \mathbb {N} \rightsquigarrow \mathbb {N} }$ ${\displaystyle (\forall n\colon g(a_{n+1}){\downarrow }=a_{n})\land g(a_{0}){\downarrow }=a_{0}}$ ${\displaystyle g}$

properties

Decidable sets are obviously retraceable ( see above ), but the reverse is generally not true. Instead:

• Retraceable sets are always either decidable or immune .
• Retraceable sets with recursively enumerable (re) complement are either decidable or even hyperimmune .

Nevertheless, a characterization of decidable sets can be found that uses the retraceable property.

• A set is decidable if and only if both it and its complement are retraceable.

If we only consider relative decidability , the following picture emerges:

• A retraceable set is either finite (i.e. decidable per se) or relatively decidable in all of its infinite subsets.
• So it is true, is retraceable and has an infinite subset , so it follows (cf. reduction ). ${\displaystyle A}$ ${\displaystyle B\subseteq A}$ ${\displaystyle A\leq _{T}B}$

In the definition above, the behavior of the retraceable function outside of indeterminate, in particular the function does not have to be defined there. However, there are cases when one can totally choose. ${\displaystyle g}$ ${\displaystyle A}$ ${\displaystyle g}$

• Retraceable sets with re complement have total retraceable functions.

Naturally there is a close connection between retraceable sets and alternative computable orders on the natural numbers.

Note : Semi-predictability should not be confused with semi-decidability .

• Every infinite semi-computable set has an infinite retraceable subset.
• Retraceable sets with right complement are semi-computable.

In the theory of Turing degrees , the retraceable sets provide a class of universal representatives:

• Each Turing degree contains a retraceable amount.
• Every recursively enumerable Turing degree contains a retraceable set whose complement is re.

Individual evidence

1. ^ JCE Dekker, J. Myhill: Retraceable sets . In: Canadian Journal of Mathematics . tape 10 . Canadian Mathematical Society, Ottawa, CAN-ON 1958, p. 357-373 .
2. ^ JCE Dekker: Infinite series of isols . In: Proceedings of Symposia in Pure Mathematics . tape 5 . American Mathematical Society, Providence, US-RI 1962, pp. 77-96 .

literature

• H. Rogers, Jr .: Theory of Recursive Functions and Effective Computability . McGraw-Hill, 1967, ISBN 978-0-262-68052-3 .
• P. Odifreddi : Classical Recursion Theory . Elsevier, 1989, ISBN 0-444-87295-7 .