Aufzählungsoperator

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

Aufzählungsoperator

Es sei $\{D_i{\}}_{i\in \mathbb{N}}$ eine effektive Nummerierung aller endlichen Teilmengen von $\mathbb{N}$ (bspw. $D_i=\{x_1;x_2;\dots ;x_n\}$ für $i=2^{x_1}+2^{x_2}+\dots +2^{x_n}$). Weiter sei $⟨\cdot ;\cdot ⟩:{\mathbb{N}}^2\to \mathbb{N}$ eine berechenbare Kodierungsfunktion für Paare natürlicher Zahlen.

• Eine Abbildung $\mathrm{\Psi }:𝒫(\mathbb{N})\to 𝒫(\mathbb{N})$ zwischen Teilmengen natürlicher Zahlen heiße Aufzählungsoperator, falls es eine rekursiv aufzählbare Menge $S\subseteq \mathbb{N}$ gibt, so dass für beliebige Mengen $A\subseteq \mathbb{N}$ gilt: $x\in \mathrm{\Psi }(A)\iff \mathrm{\exists }i:(D_i\subseteq A\wedge ⟨i;x⟩\in S)$.

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 $A$ als Eingabe. Parallel dazu durchsucht sie den Suchraum $S$ nach passenden Einträgen $⟨i;x⟩$, wird ein solcher gefunden lautet die Ausgabe $x$. Nach und nach wird so die gesamte Menge $\mathrm{\Psi }(A)$ aufgezählt.

Aufzählbare Reduktion

• Eine Menge $B\subseteq \mathbb{N}$ heiße aufzählbar reduzierbar auf $A$ (engl.: enumeration reducible), $B{⪯}_{e}A$, falls es einen Aufzählungsoperator $\mathrm{\Psi }$ gibt, so dass $\mathrm{\Psi }(A)=B$ gilt.

Ist eine Aufzählung der Menge $A$ gegeben (sei diese berechenbar oder nicht), so vermittelt der Operator $\mathrm{\Psi }$ auch eine Aufzählung von $B$ (vgl. Reduktion (Theoretische Informatik)). Es folgt, dass die Menge $B$ rekursiv aufzählbar in $A$ 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

Es gibt einige triviale Aufzählungsoperatoren, zum Beispiel die Identität ${\mathrm{\Psi }}^I(A)=A$ oder den Links-Shift ${\mathrm{\Psi }}^L(A)=\{a+1|a\in A\}$. Konstante Operatoren sind genau dann Aufzählungsoperatoren, wenn die Zielmenge rekursiv aufzählbar ist, wie etwa ${\mathrm{\Psi }}^{c;K}(A)=K$ für das spezielle Halteproblem $K$. Auch andere berechenbare Manipulationen der Eingabemengen können durch Aufzählungsoperatoren vermittelt werden, ${\mathrm{\Psi }}^{{\pi }_2}(A)=\{y|\mathrm{\exists }x:⟨x;y⟩\in A\}$.

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

$f(0)=0;$

$f(1)=1;$

$f(n+2)=f(n)+f(n+1).$

Dies lässt sich in einen Aufzählungsoperator ${\mathrm{\Psi }}_f$ für die Graphen möglicher Lösungen $f$ umformulieren, indem man explizit den zugrunde liegenden Suchraum $S$ angibt. Zur besseren Lesbarkeit werden hier direkt die endlichen Mengen $D_i$ statt ihrer Kodnummern $i$ verwendet. Außerdem werden die Elemente der Zielmenge als kodierte Paare natürlicher Zahlen aufgefasst. Notwendig enthält $S$ dann die Elemente $⟨\mathrm{\varnothing };(0;0)⟩$ und $⟨\mathrm{\varnothing };(1;1)⟩$, da jede Lösung auf Grund der ersten beiden Gleichungen die $0$ und die $1$ jeweils auf sich selbst abbilden muss. Außerdem enthalte $S$ für beliebige natürliche Zahlen $n;m;k\in \mathbb{N}$ jeweils das Paar $⟨\{(n;m);(n+1;k)\};(n+2;m+k)⟩$. Dies realisiert die dritte Gleichung, denn ist durch die Eingabemenge nun die Information bekannt, dass für die angepeilte Lösung $n\mapsto m$ und $n+1\mapsto k$ gilt, dann erzwingt ${\mathrm{\Psi }}_f$ auch $n+2\mapsto m+k$ für die Ausgabemenge.

Eigenschaften

• Es gibt eine effektive Nummerierung $\{{\mathrm{\Psi }}_p{\}}_{p\in \mathbb{N}}$ aller Aufzählungsoperatoren, diese ergibt sich sofort aus der kanonischen Nummerierung aller rekursiv aufzählbaren Mengen.

Für einen Aufzählungsoperator $\mathrm{\Psi }$, Mengen $A;B\subseteq \mathbb{N}$ und natürliche Zahlen $x$ gilt:

• Monotonie: $A\subseteq B\Rightarrow \mathrm{\Psi }(A)\subseteq \mathrm{\Psi }(B)$.
• Kompaktheit: $x\in \mathrm{\Psi }(A)\Rightarrow \mathrm{\exists }D{\subset }_{\text{fin}}A:x\in \mathrm{\Psi }(D)$.

Aus der Kompaktheit folgt außerdem, dass Aufzählungsoperatoren als Abbildungen stetig sind, wenn man die Potenzmenge $𝒫(\mathbb{N})$ mit der Topologie versieht, die durch die Basismengen $\{A\subseteq \mathbb{N}|D_i{\subset }_{\text{fin}}A{\}}_{i\in \mathbb{N}}$ erzeugt wird.

• Es gibt eine total berechenbare Funktion $g$, so dass $\mathrm{\forall }p;q:{\mathrm{\Psi }}_{g(⟨p;q⟩)}={\mathrm{\Psi }}_p\circ {\mathrm{\Psi }}_q$.
  • Insbesondere ist also die Klasse der Aufzählungsoperatoren unter Komposition abgeschlossen.
• Wie alle Reduktionen ist ${⪯}_e$ eine Präordnung auf $𝒫(\mathbb{N})$, die Relation also insbesondere transitiv.
• Die Truth-table-Reduktion (und damit auch die Many-one-Reduktion) impliziert die aufzählbare Reduktion, $B{⪯}_{1}A\Rightarrow B{⪯}_{m}A\Rightarrow B{⪯}_{tt}A\Rightarrow B{⪯}_{e}A$.

Die Implikationen sind dabei jeweils strikt.

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

Berechenbare Operatoren

Eine Menge $A\subseteq \mathbb{N}$ natürlicher Zahlen heiße rechtseindeutig, falls gilt: $⟨x;y⟩;⟨x;z⟩\in A\Rightarrow y=z$. Es bezeichne $𝔓$ die Menge aller partiellen Abbildungen $\psi :\mathbb{N}⇝\mathbb{N}$ natürlicher Zahlen. Identifiziert man eine Funktion $\psi \in 𝔓$ mit ihrem Graphen, so erlaubt $⟨\cdot ;\cdot ⟩$ diese als Teilmenge der natürlichen Zahlen aufzufassen. Dadurch ist eine Einbettung $𝔓\hookrightarrow 𝒫(\mathbb{N});\psi \mapsto \{⟨x;\psi (x)⟩|x\in \mathrm{dom}(\psi )\}$ erklärt. Ihr Bild besteht gerade aus den rechtseindeutigen Mengen.

Gilt nun für einen Aufzählungsoperator $\mathrm{\Psi }(𝔓)\subseteq 𝔓$, überführt er also rechtseindeutige Mengen wieder in rechtseindeutige, so ist die Einschränkung $\mathrm{\Psi }{|}_{𝔓}$ ein berechenbarer Operator. Auf diese Weise erhält man alle berechenbaren Operatoren. Notwendig bildet $\mathrm{\Psi }$ dann auch berechenbare Funktionen wieder auf berechenbare ab.

Rekursionssatz

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 $\mathrm{\Psi }$ gibt es eine rekursiv aufzählbare Menge $F\subseteq \mathbb{N}$ derart, dass $F$ ein Fixpunkt ist, $\mathrm{\Psi }(F)=F$, und jeder Fixpunkt von $\mathrm{\Psi }$ die Menge $F$ enthält.
• Ist $\mathrm{\Psi }{|}_{𝔓}$ sogar ein berechenbarer Operator, so gibt es eine partiell berechenbare Funktion $\psi$, so dass $\mathrm{\Psi }(\psi )=\psi$ und jeder rechtseindeutige Fixpunkt von $\mathrm{\Psi }$ die Funktion $\psi$ als Einschränkung besitzt.

Der Fixpunkt $F$ lässt sich sogar explizit angeben: Es sei $F_0=\mathrm{\varnothing }$ und für jede natürliche Zahl $k$ sei $F_{k+1}=F_k\cup \mathrm{\Psi }(F_k)$, dann ist $F=\bigcup _k{F}_k$. Der zweite Teil folgt nun aus dem ersten durch die Beobachtung, dass in diesem Fall die Menge $F$ rechtseindeutig ist.

Betrachtet man beispielsweise den oben definierten Operator ${\mathrm{\Psi }}_f$, so erhält man als den kleinsten Fixpunkt den Graphen der durch die Gleichungen eindeutig definierten Fibonacci-Funktion $\mathrm{fib}$. Ein weiterer, allerdings nicht mehr rechtseindeutiger, Fixpunkt ist die Menge $\{⟨x;y⟩|y\le \mathrm{fib}(x)\}$, da auch sie den obigen Gleichungen genügt. Der Fixpunkt enthält offenbar den Graphen von $\mathrm{fib}$ als Teilmenge.

Quellen

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur