Kreative und produktive Mengen

(Weitergeleitet von Produktive Menge)

Kreative und produktive Mengen sind Klassen von Teilmengen der natürlichen Zahlen, die in der Berechenbarkeitstheorie und der mathematischen Logik auftreten. Sie sind eng mit dem Begriff der rekursiven Aufzählbarkeit (RE) verbunden: Die produktiven Mengen sind in einem gewissen Sinne die noch am besten algorithmisch beherrschbaren Mengen, die nicht mehr rekursiv aufzählbar sind. Dagegen sind die kreativen Mengen genau die RE-vollständigen (vgl. Vollständigkeit (Theoretische Informatik)). Die Bezeichnung kreative Menge geht auf einen Aufsatz von Emil Post aus dem Jahre 1944 zurück[1], erst später kam eine eigene Bezeichnung für die produktiven Mengen hinzu.[2]

Definition

Bearbeiten

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

Eine Menge   natürlicher Zahlen heiße produktiv, falls es eine partielle berechenbare Funktion   gibt, die folgender Eigenschaft genügt:

 

Wann immer also eine rekursiv aufzählbare Menge ganz in   liegt, wird ihr Index auf ein Element von   abgebildet, dass nicht mehr Teil dieser Menge ist. Insbesondere ist   an dieser Stelle definiert.

In diesem Fall wird   eine produktive Funktion für   genannt.

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

Beispiele

Bearbeiten
  • Das spezielle Halteproblem   ist der Prototyp einer kreativen Menge[1], sein Komplement   ist produktiv mit der Identität als produktiver Funktion.
  • Die Klasse   aller gültigen arithmetischen Formeln – durch eine geeignete Gödelisierung als Menge natürlicher Zahlen aufgefasst – ist produktiv, dies besagt der Erste Gödelsche Unvollständigkeitssatz.
  • Die Menge   der Indizes aller total berechenbaren Funktionen ist ebenfalls produktiv.

Eigenschaften

Bearbeiten
  • Die produktive Funktion lässt sich stets total und injektiv wählen.
  • Produktive Mengen sind nicht rekursiv aufzählbar, für jede rekursiv aufzählbare Menge   bezeugt ja  , dass   gilt.
  • Allerdings besitzt jede produktive Menge eine unendliche, rekursiv aufzählbare Teilmenge.
    • Insbesondere sind also produktive Mengen stets unendlich.
  • Kreative Mengen sind nicht entscheidbar, denn dazu müsste ihr Komplement rekursiv aufzählbar sein.
  • Eine Menge ist genau dann produktiv, wenn ihr Komplement RE-schwer ist – vgl. Schwere (Theoretische Informatik). Dies ist der Satz von Myhill.
    • Eine Menge ist daher genau dann kreativ, wenn sie RE-vollständig ist.
  • Ist eine Menge   produktiv, so auch die Menge  .
  • Seien   zwei Mengen mit  , d. h.   sei auf   many-one-reduzierbar, dann gilt:
    • Ist   produktiv, so auch  .
    • Ist   kreativ, so ist   genau dann kreativ, wenn   produktiv ist.

Literatur

Bearbeiten
  • R. Soare: Recursively enumerable sets and degrees: A study of computable functions and computably generated sets. In: Perspectives in Mathematical Logic, 1987, Springer, Berlin. ISBN 3-540-15299-7.
  • H. Rogers jr.: Theory of recursive functions and effective computability. 2nd ed., 1987, MIT Press, Cambridge MA. ISBN 0-262-68052-1.
  • M. Grohe: Vorlesung Berechenbarkeit. Kap. 5 § 3, Sommersemester 2010, Humboldt-Universität Berlin (online, PDF-Datei; 81 kB).

Einzelnachweise

Bearbeiten
  1. a b E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, vol. 50 (1944), no. 5, pp. 284–316 (online, PDF-Datei; 4,0 MB).
  2. J. Dekker: Productive sets. Transaction of the American Mathematical Society, vol. 78 (1955), no. 1, pp. 129–149 (online, PDF-Datei; 2,0 MB).