Retraceable Menge

Eine Menge natürlicher Zahlen heißt retraceable (engl.: zurückverfolgbar), wenn zu jedem Element der Menge das nächstkleinere Element berechnet werden kann. Retraceable Mengen treten in der theoretischen Informatik, genauer der Berechenbarkeitstheorie, bei der Untersuchung entscheidbarer Mengen auf. Die Theorie der retraceablen Mengen geht auf Arbeiten von Dekker und Myhill zurück.

Erklärung

Motivation

Für entscheidbare Mengen $A=\{a_{0}<a_{1}<a_{2}<\dots \}\subseteq \mathbb {N}$ sind die folgenden beiden Funktionen $f$ und $g$ stets berechenbar:

1. Für alle $n$ sei $f(a_{n})=a_{n+1}$, es sei denn $A$ ist endlich und $a_{n}=\max A$, dann gelte $f(a_{n})=a_{n}$.
2. Für alle $n$ sei $g(a_{n+1})=a_{n}$ sowie $g(a_{0})=a_{0}$.

Außerhalb von $A$ können die Funktionen dabei ein beliebiges Verhalten zeigen. Nun ist die in 1. definierte Funktion $f$ genau dann berechenbar, wenn $A$ entscheidbar ist. Es stellt sich daher die Frage, ob eine ähnliche Charakterisierung auch für diejenigen Mengen gelingt, für die $g$ berechenbar ist. Dies sind gerade die retraceable Mengen.

Definition

Eine Menge $A=\{a_{0}<a_{1}<a_{2}<\dots \}\subseteq \mathbb {N}$ natürlicher Zahlen heiße retraceable, falls es eine partiell berechenbare Funktion $g\colon \mathbb {N} \rightsquigarrow \mathbb {N}$ gibt, so dass $(\forall n\colon g(a_{n+1}){\downarrow }=a_{n})\land g(a_{0}){\downarrow }=a_{0}$. Die Abbildung $g$ heißt dann retraceable Funktion.

Eigenschaften

Entscheidbare Mengen sind offensichtlich retraceable (s. o.), allerdings gilt die Umkehrung im Allgemeinen nicht. Stattdessen gilt:

• Retraceable Mengen sind stets entweder entscheidbar order immun.
• Retraceable Mengen mit rekursiv aufzählbarem (r.e.) Komplement sind entweder entscheidbar oder sogar hyperimmun.

Dennoch lässt sich eine Charakterisierung entscheidbarer Mengen finden, die die retraceable Eigenschaft benutzt.

• Eine Menge ist genau dann entscheidbar, wenn sowohl sie selbst als auch ihr Komplement retraceable ist.

Betrachtet man nur relative Entscheidbarkeit ergibt sich das folgende Bild:

• Eine retraceable Menge ist entweder endlich (also per se entscheidbar) oder in allen ihren unendlichen Teilmengen relativ entscheidbar.
• Es gilt also, ist $A$ retraceable und hat eine unendliche Teilmenge $B\subseteq A$, so folgt $A\leq _{T}B$ (vgl. Reduktion).

In der obigen Definition ist das Verhalten der retraceable Funktion $g$ außerhalb von $A$ unbestimmt, insbesondere muss die Funktion dort nicht definiert sein. Es gibt jedoch Fälle, in denen man $g$ total wählen kann.

• Retraceable Mengen mit r.e. Komplement haben totale retraceable Funktionen.

Natürlicherweise gibt es einen engen Zusammenhang zwischen retraceable Mengen und alternativen berechenbaren Ordnungen auf den natürlichen Zahlen.

Hinweis: Semi-Berechenbarkeit sollte nicht mit Semi-Entscheidbarkeit verwechselt werden.

• Jede unendliche semi-berechenbare Menge hat eine unendliche retraceable Teilmenge.
• Retraceable Mengen mit r.e. Komplement sind semi-berechenbar.

In der Theorie der Turing-Grade liefern die retraceable Mengen eine Klasse universeller Repräsentanten:

• Jeder Turing-Grad enthält eine retraceable Menge.
• Jeder rekursiv aufzählbare Turing-Grad enthält eine retraceable Menge, deren Komplement r.e. ist.

Literatur

• 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.