Einfache und immune Mengen

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Immune Menge)
Zur Navigation springen Zur Suche springen

Einfache und immune Mengen sind Klassen von Teilmengen der natürlichen Zahlen und liefern wichtige Gegenbeispiele in der Berechenbarkeitstheorie. Sie sind eng mit dem Begriff der rekursiven Aufzählbarkeit (RE) verbunden: Während immune Mengen genau die abzählbar unendlichen Mengen natürlicher Zahlen sind, die keine unendliche rekursiv aufzählbare Teilmenge besitzen, sind die einfachen Mengen die rekursiv aufzählbaren Komplemente immuner Mengen. Die Definitionen lassen sich weiter verstärken und führen so auf den Begriff der hyper- oder gar hyperhypereinfachen Mengen.

Emil Post vermutete bereits in den 1940er-Jahren die Existenz einfacher Mengen, doch erst 1956 bzw. 1957 konnte dies (unabhängig voneinander) von Richard Friedberg und Albert Muchnik auch bewiesen werden.

Es sei eine effektive Nummerierung aller rekursiv aufzählbarer Mengen.

Eine Menge natürlicher Zahlen heiße immun, falls gilt .

(d. h. ist abzählbar unendlich, besitzt aber keine unendliche rekursiv aufzählbare Teilmenge). Hier bezeichne die Kardinalität einer Menge.

Eine Menge heiße nun einfach, falls sie selbst rekursiv aufzählbar und ihr Komplement immun ist.

Als Post 1944 begann, Probleme nach ihrer Entscheidbarkeit zu vergleichen[1], stellte sich schnell die Frage, ob jede rekursiv aufzählbare Menge, die nicht mehr entscheidbar ist, automatisch schon vollständig für die aufzählbaren Mengen ist. Nun besitzen Komplemente RE-vollständiger Mengen (genauer alle produktiven Mengen) eine unendliche aufzählbare Teilmenge. Das heißt, die Existenz von einfachen Mengen ist bereits hinreichend für die negative Beantwortung der obigen Frage. Post selbst vermutete diese Existenz, konnte sie allerdings noch nicht beweisen. Erst als Friedberg[2] und Muchnik[3] 1956/57 das (allgemeinere) Postsche Problem lösten, konstruierten sie en passant die erste einfache Menge. Dies war außerdem der erste Beweis in der Geschichte der Berechenbarkeitstheorie, der mit Hilfe der Prioritätsmethode geführt wurde. Heute sind dagegen deutlich simplere Konstruktionen einfacher Mengen bekannt.

Nach Voraussetzung gibt es eine Turing-Maschine (oder einen Algorithmus in einem alternativen Berechenbarkeitsmodell), die bei Eingabe die Menge aufzählt. Sei nun diejenige partielle Zahlfunktion, bei der stets das erste von gefundene Element ist, für das gilt, falls ein solches existiert. Dann ist offenbar (partiell) berechenbar und ihr Wertebereich ist einfach.

Analog lassen sich so auch weitere einfache Mengen konstruieren.[4]

  • Immune Mengen sind nicht rekursiv aufzählbar, andernfalls würden sie ja sich selbst als unendliche aufzählbare Teilmenge enthalten.
  • Eine unendliche Menge ist genau dann immun, wenn sie keine unendliche entscheidbare Teilmenge enthält.
  • Einfache Mengen sind daher nicht entscheidbar.
  • Immune Mengen sind per Konstruktion nicht produktiv und einfache Mengen daher auch nicht kreativ.
  • Nach dem Satz von Myhill sind einfache Mengen also nicht RE-vollständig.
  • Es gibt ein Paar einfacher Mengen, das die natürlichen Zahlen ausschöpft .[5]

Hypereinfache und hyperimmune Mengen

[Bearbeiten | Quelltext bearbeiten]

Man sagt, eine geordnete Menge natürlicher Zahlen werde durch eine Zahlenfunktion majorisiert, falls gilt, der Funktionswert also stets mindestens so groß ist wie der -kleinste Wert von .

Eine Menge heiße hyperimmun (h.i.), falls sie von keiner total berechenbaren Funktion majorisiert wird.
Eine Menge heiße dann hypereinfach (h.s.; von engl. hypersimple), falls sie rekursiv aufzählbar und ihr Komplement h.i. ist.
  • Hypereinfache Mengen sind notwendig unendlich.
  • Hyperimmune Mengen sind stets immun und hypereinfache Mengen daher immer auch einfach.
  • Es gibt einfache Mengen, die nicht hypereinfach sind.[6]
  • Der Schnitt zweier hypereinfacher Mengen ist wieder hypereinfach.
  • Die Vereinigung einer hyperimmunen mit einer immunen Menge ist wieder hyperimmun.

Hyperhypereinfache und hyperhyperimmune Mengen

[Bearbeiten | Quelltext bearbeiten]

Es gibt eine Charakterisierung von h.i. Mengen, die gelegentlich auch als alternative Definition verwendet wird:

Es sei dafür eine effektive Nummerierung aller endlichen Teilmengen von (bspw. für ).

Eine unendliche Menge ist nun genau dann hyperimmun, wenn es keine total berechenbare Funktion gibt, so dass gilt.

Mit anderen Worten ist eine unendliche Menge also h.i., wenn es keine – in kanonischen Indizes – berechenbare Liste von paarweise disjunkten endlichen Mengen gibt, die alle schneiden.

Wenn man nun von den kanonischen -Indizes zu den oben eingeführten allgemeineren -Indizes übergeht, ergibt sich die Definition von hyperhyperimmunen Mengen. Es stellte sich heraus, dass diese sogar echt stärker ist.

Eine unendliche Menge heiße hyperhyperimmun (h.h.i.), falls es keine total berechenbare Funktion gibt, so dass für jedes die Menge endlich ist und gilt.

Eine Menge ist h.h.i. falls sie unendlich ist und es keine – in -Indizes – berechenbare Liste von paarweise disjunkten endlichen Mengen gibt, die diese Menge alle schneiden.

Eine Menge Menge heiße dann hyperhypereinfach (h.h.s.), falls sie rekursiv aufzählbar und ihr Komplement h.h.i. ist.
  • Hyperhyperimmune Mengen sind stets hyperimmun, da sich -Indizes berechenbar in -Indizes umwandeln lassen.
  • Es gibt hyperimmune Mengen, die nicht hyperhyperimmun sind.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, Ausg. 50 (1944), No. 5, S. 284–316 (online, PDF-Datei; 4,0 MB).
  2. R. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944). In: Proceedings of the National Academy of Sciences. Band 43, S. 236–238 (pnas.org [PDF]).
  3. A. Muchnik: Über die Unlösbarkeit des Problems der Reduzierbarkeit in der Theorie der Algorithmen. (russisch). In: Doklady Akademii Nauk SSSR (N.S.). Band 108, 1956, S. 194–197.
  4. Setze mit analog zu , allerdings mit .
  5. Setze dazu und , mit aus dem obigen Beispiel.
  6. Nehme dazu die Menge aus dem obigen Beispiel, sie ist einfach, aber ihr Komplement wird durch majorisiert.