Aufzählungsoperatoren (engl.: enumeration operator) sind in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte berechenbare Abbildungen zwischen Mengen natürlicher Zahlen. Sie sind damit eine Verallgemeinerung von berechenbaren Operatoren. Aufzählungsoperatoren definieren eine Reduktion zwischen den beteiligten Mengen.

Definition

Bearbeiten

Aufzählungsoperator

Bearbeiten

Es sei   eine effektive Nummerierung aller endlichen Teilmengen von   (bspw.   für  ). Weiter sei   eine berechenbare Kodierungsfunktion für Paare natürlicher Zahlen.

  • Eine Abbildung   zwischen Teilmengen natürlicher Zahlen heiße Aufzählungsoperator, falls es eine rekursiv aufzählbare Menge   gibt, so dass für beliebige Mengen   gilt:  .

Aufzählungsoperatoren lassen sich offenbar von Turing-Maschinen realisieren: Die entsprechende Maschine erhält von einer externen Quelle – zum Beispiel einem menschlichen Nutzer – immer größere, endliche Teilmengen von   als Eingabe. Parallel dazu durchsucht sie den Suchraum   nach passenden Einträgen  , wird ein solcher gefunden lautet die Ausgabe  . Nach und nach wird so die gesamte Menge   aufgezählt.

Aufzählbare Reduktion

Bearbeiten
  • Eine Menge   heiße aufzählbar reduzierbar auf   (engl.: enumeration reducible),  , falls es einen Aufzählungsoperator   gibt, so dass   gilt.

Ist eine Aufzählung der Menge   gegeben (sei diese berechenbar oder nicht), so vermittelt der Operator   auch eine Aufzählung von   (vgl. Reduktion (Theoretische Informatik)). Es folgt, dass die Menge   rekursiv aufzählbar in   ist (vgl. Orakel-Turingmaschine), die Umkehrung gilt im Allgemeinen nicht. Aufzählungsoperatoren bilden daher stets rekursiv aufzählbare Mengen wieder auf rekursiv aufzählbare Mengen ab, dies motiviert die Bezeichnung.

Beispiele

Bearbeiten

Es gibt einige triviale Aufzählungsoperatoren, zum Beispiel die Identität   oder den Links-Shift  . Konstante Operatoren sind genau dann Aufzählungsoperatoren, wenn die Zielmenge rekursiv aufzählbar ist, wie etwa   für das spezielle Halteproblem  . Auch andere berechenbare Manipulationen der Eingabemengen können durch Aufzählungsoperatoren vermittelt werden,  .

Die eigentliche Intention der obigen Definition ist aber ein berechenbares Analogon zu induktiven Definitionen zu schaffen. Eine Menge induktiver Gleichungen könnte beispielsweise wie folgt lauten (vgl. Fibonacci-Folge):

 
 
 

Dies lässt sich in einen Aufzählungsoperator   für die Graphen möglicher Lösungen   umformulieren, indem man explizit den zugrunde liegenden Suchraum   angibt. Zur besseren Lesbarkeit werden hier direkt die endlichen Mengen   statt ihrer Kodnummern   verwendet. Außerdem werden die Elemente der Zielmenge als kodierte Paare natürlicher Zahlen aufgefasst. Notwendig enthält   dann die Elemente   und  , da jede Lösung auf Grund der ersten beiden Gleichungen die   und die   jeweils auf sich selbst abbilden muss. Außerdem enthalte   für beliebige natürliche Zahlen   jeweils das Paar  . Dies realisiert die dritte Gleichung, denn ist durch die Eingabemenge nun die Information bekannt, dass für die angepeilte Lösung   und   gilt, dann erzwingt   auch   für die Ausgabemenge.

Eigenschaften

Bearbeiten
  • Es gibt eine effektive Nummerierung   aller Aufzählungsoperatoren, diese ergibt sich sofort aus der kanonischen Nummerierung aller rekursiv aufzählbaren Mengen.

Für einen Aufzählungsoperator  , Mengen   und natürliche Zahlen   gilt:

  • Monotonie:  .
  • Kompaktheit:  .

Aus der Kompaktheit folgt außerdem, dass Aufzählungsoperatoren als Abbildungen stetig sind, wenn man die Potenzmenge   mit der Topologie versieht, die durch die Basismengen   erzeugt wird.

  • Es gibt eine total berechenbare Funktion  , so dass  .
    • Insbesondere ist also die Klasse der Aufzählungsoperatoren unter Komposition abgeschlossen.
  • Wie alle Reduktionen ist   eine Präordnung auf  , die Relation also insbesondere transitiv.
  • Die Truth-table-Reduktion (und damit auch die Many-one-Reduktion) impliziert die aufzählbare Reduktion,  .

Die Implikationen sind dabei jeweils strikt.

  • Die aufzählbare Reduktion und die Turing-Reduktion sind dagegen unvergleichbar.

Berechenbare Operatoren

Bearbeiten

Eine Menge   natürlicher Zahlen heiße rechtseindeutig, falls gilt:  . Es bezeichne   die Menge aller partiellen Abbildungen   natürlicher Zahlen. Identifiziert man eine Funktion   mit ihrem Graphen, so erlaubt   diese als Teilmenge der natürlichen Zahlen aufzufassen. Dadurch ist eine Einbettung   erklärt. Ihr Bild besteht gerade aus den rechtseindeutigen Mengen.

Gilt nun für einen Aufzählungsoperator  , überführt er also rechtseindeutige Mengen wieder in rechtseindeutige, so ist die Einschränkung   ein berechenbarer Operator. Auf diese Weise erhält man alle berechenbaren Operatoren. Notwendig bildet   dann auch berechenbare Funktionen wieder auf berechenbare ab.

Rekursionssatz

Bearbeiten

Es gibt einen Rekursionssatz für Aufzählungsoperatoren. Dieser ist schwächer als der entsprechende Satz für berechenbare Operatoren, weshalb er in der englischen Literatur auch gelegentlich als weak recursion theorem bezeichnet wird.

  • Für jeden Aufzählungsorperator   gibt es eine rekursiv aufzählbare Menge   derart, dass   ein Fixpunkt ist,  , und jeder Fixpunkt von   die Menge   enthält.
  • Ist   sogar ein berechenbarer Operator, so gibt es eine partiell berechenbare Funktion  , so dass   und jeder rechtseindeutige Fixpunkt von   die Funktion   als Einschränkung besitzt.

Der Fixpunkt   lässt sich sogar explizit angeben: Es sei   und für jede natürliche Zahl   sei  , dann ist  . Der zweite Teil folgt nun aus dem ersten durch die Beobachtung, dass in diesem Fall die Menge   rechtseindeutig ist.

Betrachtet man beispielsweise den oben definierten Operator  , so erhält man als den kleinsten Fixpunkt den Graphen der durch die Gleichungen eindeutig definierten Fibonacci-Funktion  . Ein weiterer, allerdings nicht mehr rechtseindeutiger, Fixpunkt ist die Menge  , da auch sie den obigen Gleichungen genügt. Der Fixpunkt enthält offenbar den Graphen von   als Teilmenge.

  • Sharma Jain et al.: Systems That Learn. 2nd Auflage. MIT Press, Cambridge, Massachusetts 1999, ISBN 0-262-10077-0, S. 19 (englisch).
  • Stephen C. Kleene: Introduction to Metamathematics. North-Holland Publishing Company, New York City, New York 1952, S. 352–353 (englisch).
  • Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1987, ISBN 0-262-68052-1, S. 145–149 (englisch).