Retraceable Menge

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.[1][2]

Für entscheidbare Mengen sind die folgenden beiden Funktionen und stets berechenbar:

  1. Für alle sei , es sei denn ist endlich und , dann gelte .
  2. Für alle sei sowie .

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

Eine Menge natürlicher Zahlen heiße retraceable, falls es eine partiell berechenbare Funktion gibt, so dass . Die Abbildung heißt dann retraceable Funktion.

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

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 retraceable und hat eine unendliche Teilmenge , so folgt (vgl. Reduktion).

In der obigen Definition ist das Verhalten der retraceable Funktion außerhalb von unbestimmt, insbesondere muss die Funktion dort nicht definiert sein. Es gibt jedoch Fälle, in denen man 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:

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. J.C.E. Dekker, J. Myhill: Retraceable sets. In: Canadian Journal of Mathematics. Band 10. Canadian Mathematical Society, Ottawa, CAN-ON 1958, S. 357–373.
  2. J.C.E. Dekker: Infinite series of isols. In: Proceedings of Symposia in Pure Mathematics. Band 5. American Mathematical Society, Providence, US-RI 1962, S. 77–96.