Aufzählungsoperator

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Aufzählbare Reduktion)
Zur Navigation springen Zur Suche springen

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.

Aufzählungsoperator

[Bearbeiten | Quelltext 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 | Quelltext 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.

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.

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

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