Kreative und produktive Mengen

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

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]

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.

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