Berechenbarer Operator

Berechenbare Operatoren (auch: effektive Operatoren; engl.: recursive operator, effective operator) sind in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, Manipulationen partieller Funktionen, die durch Turing-Maschinen realisiert werden. Berechenbare Funktionale sind durch Turing-Maschinen vermittelte Zuordnungen von Funktionen zu natürlichen Zahlen. Berechenbare Funktionale werden benötigt, um berechenbare Operatoren mathematisch exakt zu definieren. Neben ihrer eigenständigen Bedeutung in der Berechenbarkeitstheorie bilden berechenbare Operatoren die technische Grundlage der algorithmischen Lerntheorie. Berechenbare Operatoren bilden einen Spezialfall der Aufzählungsoperatoren.

Definition

Es bezeichne im Folgenden ${\mathfrak {P}}$ die Menge aller partiellen Abbildungen $\psi \colon \mathbb {N} \rightsquigarrow \mathbb {N}$ natürlicher Zahlen, ${\mathfrak {R}}$ bezeichne die Teilmenge der totalen Funktionen. Weiter sei $\langle \cdot \rangle$ eine berechenbare Kodierungsfunktion für endliche Tupel natürlicher Zahlen (bspw. die Cantorsche Paarungsfunktion). Identifiziert man eine Funktion $\psi \in {\mathfrak {P}}$ mit ihrem Graphen, so erlaubt $\langle \cdot \rangle$ wiederum, diese als Teilmenge der natürlichen Zahlen aufzufassen: $\psi =\{\langle x;\psi (x)\rangle |x\in \operatorname {dom} (\psi )\}\subseteq \mathbb {N}$.

Intuitive Fassung

• Ein Operator $\Theta \colon {\mathfrak {P}}\to {\mathfrak {P}}$ heiße berechenbar, falls es eine Turing-Maschine gibt, die für beliebige (nicht notwendigerweise selbst berechenbare) Aufzählungen des Graphens $\psi$ als Eingabe ihrerseits den Graphen von $\Theta (\psi )$ aufzählt.
• Er heiße total berechenbar bzw. allgemein berechenbar (engl.: total recursive, general recursive), falls er zusätzlich totale Funktionen wieder in totale Funktionen überführt, $\Theta ({\mathfrak {R}})\subseteq {\mathfrak {R}}$.

Für diese Definition muss die Arbeitsweise einer Turing-Maschine leicht modifiziert werden: Statt einer einzelnen natürlichen Zahl erhält sie nun sukzessive immer längere, endliche Anfangsstücke der entsprechenden Aufzählung von $\psi$ als Eingabe. Diese Definition lässt sich leicht (bspw. durch multiple Eingabebänder) auf Operatoren $\Theta \colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l}\to {\mathfrak {P}}$ für beliebige Stelligkeiten $k;l\in \mathbb {N}$ erweitern.

Formale Fassung

Es sei $\{\sigma _{i}\}_{i\in \mathbb {N} }$ eine effektive Nummerierung aller partiellen Funktionen mit endlichem Definitionsbereich. Für jede rekursiv aufzählbare Menge $A\subseteq \mathbb {N}$ sei eine berechenbare Aufzählung $\nu _{A}\colon \mathbb {N} \to \mathbb {N}$ mit Bildmenge $\operatorname {im} (\nu _{A})=A$ bzw. $\nu _{\emptyset }=\bot$ fixiert.

• Ein Funktional $F\colon {\mathfrak {P}}\times \mathbb {N} \rightsquigarrow \mathbb {N}$ heiße berechenbar, falls es eine rekursiv aufzählbare Menge $A$ gibt, so dass für alle partielle Funktionen $\psi$ und natürliche Zahlen $x\in \mathbb {N}$ gilt: $F(\psi ;x){\downarrow }\Leftrightarrow \exists i;z\colon (\sigma _{i}\subseteq \psi \land \langle i;x;z\rangle \in A)$.

In diesem Fall ist dann $F(\psi ;x)=z$ für das erste solche Tripel $\langle i;x;z\rangle$, das von $\nu _{A}$ aufgezählt wird.

• $F$ heiße total berechenbar wenn es berechenbar und für totale Funktionen selbst total ist, also $\psi \in {\mathfrak {R}}\Rightarrow \forall x\colon F(\psi ;x){\downarrow }$.

Entsprechendes gilt für Funktionale $F\colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l}\rightsquigarrow \mathbb {N}$.

• Ein Operator $\Theta \colon {\mathfrak {P}}\to {\mathfrak {P}}$ heiße berechenbar falls es ein berechenbares Funktional $F\colon {\mathfrak {P}}\times \mathbb {N} \rightsquigarrow \mathbb {N}$ derart gibt, dass für beliebige partielle Funktionen $\psi$ und natürliche Zahlen $x$ gilt: $\Theta (\psi )(x)=F(\psi ;x)$.
• $\Theta$ heiße total berechenbar, falls der Operator totale Funktionen auf totale abbildet, $\psi \in {\mathfrak {R}}\Rightarrow \forall x\colon \Theta (\psi )(x){\downarrow }$.

Analog werden Operatoren $\Theta \colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l}\to {\mathfrak {P}}$ durch Funktionale $F\colon {\mathfrak {P}}^{k}\times \mathbb {N} ^{l+1}\rightsquigarrow \mathbb {N}$ definiert.

Erläuterung

Durch die Nummerierung der $\sigma _{i}$ erhält die rekursiv aufzählbare Menge $A$ den Charakter eines Suchraums. Zur Berechnung des entsprechenden Funktionals $F$ wird nach Einträgen zu endlichen Einschränkungen der Funktion $\psi$ gesucht. Falls kein passender Eintrag gefunden wird, terminiert die Berechnung nie und das Funktional bleibt an dieser Stelle undefiniert. Die Fixierung der aufzählenden Prozedur $\nu _{A}$ sichert, dass $F$ wohldefiniert ist.

Die Eingabefunktion $\psi$ wird von einer externen Quelle zur Verfügung gestellt, weshalb weder die Funktion selbst noch die gewählte Aufzählung berechenbar zu sein braucht. Dies lässt sich so interpretieren, dass die Turing-Maschine während der Berechnung einen menschlichen Nutzer zur Eingabe immer neuer Paare $\langle x;\psi (x)\rangle$ auffordert. In anderen Worten lernt die Turing-Maschine die Eingabefunktion und transformiert diese gleichzeitig. Die obige Definition sichert, dass das Ergebnis dieser Manipulation nicht von der Reihenfolge abhängt in der der Graph von $\psi$ präsentiert wird.

Während effektive Operatoren stets total sind, braucht dies für die zugrunde liegenden Funktionale nicht zu gelten, denn ggf. gibt es nicht-totale Funktionen im Bild des Operators. Es ist daher zu beachten, dass es Operatoren gibt, die total und berechenbar sind, aber nicht total berechenbar im Sinne der Definition. Ein Beispiel ist der konstante Operator, der jede Funktion auf die überall undefinierte Funktion $\bot$ abbildet, dieser ist berechenbar mit der Wahl $A=\emptyset$.

Beispiele

• Ein konstanter Operator ist genau dann effektiv, wenn die Zielfunktion berechenbar ist, bspw. $\Theta ^{c;S}(\psi )=(x\mapsto x+1)$ die Nachfolgerfunktion.
• Identität: $\Theta ^{I}(\psi )=\psi$.
• Links-Shift: $\Theta ^{L}(\psi )(x)=\psi (x+1)$.
• Auswertung an der Stelle $0$: $F^{E}(\psi ;x)=\psi (0)$.

Eigenschaften

Es bezeichne ${\mathcal {P}}\subsetneq {\mathfrak {P}}$ die Klasse der berechenbaren Funktionen und analog ${\mathcal {R}}\subsetneq {\mathfrak {R}}$ die Teilmenge der total berechenbaren Abbildungen. Außerdem sei $\{\varphi _{p}\}_{p\in \mathbb {N} }$ eine effektive Nummerierung von ${\mathcal {P}}$ (bspw. die Gödel-Nummerierung aller deterministischen Turing-Maschinen), daher ist durch $\forall p\colon W_{p}=\operatorname {dom} (\varphi _{p})$ die kanonische Nummerierung aller rekursiv aufzählbaren Mengen gegeben.

Aus der obigen Definition ergeben sich sofort einige wichtige Eigenschaften:

• Es gibt eine effektive Nummerierung $\{\Theta _{p}\}_{p\in \mathbb {N} }$ aller berechenbaren Operatoren, nämlich durch die Setzung $A=W_{p}$.
• Für jeden berechenbaren Operator gibt es eine total berechenbare Funktion $f\in {\mathcal {R}}$, so dass $\forall p\colon \Theta (\varphi _{p})=\varphi _{f(p)}$.
  • Insbesondere überführen berechenbare Operatoren berechenbare Funktionen wieder in berechenbare Funktionen, $\Theta ({\mathcal {P}})\subseteq {\mathcal {P}}$, dies motiviert die Bezeichnung.
  • Für allgemein berechenbare Operatoren gilt zusätzlich $\Theta ({\mathcal {R}})\subseteq {\mathcal {R}}$.
• Die Komposition (allgemein) berechenbarer Operatoren ist wieder (allgemein) berechenbar.
  • Es gibt sogar eine total berechenbare Funktion $g\in {\mathcal {R}}$, so dass $\forall p;q\colon \Theta _{g(\langle p;q\rangle )}=\Theta _{p}\circ \Theta _{q}$.

Für berechenbare Operatoren $\Theta$, partielle Funktionen $\psi$ und natürliche Zahlen $x$ gilt:

• Monotonie: $\Theta (\psi )(x){\downarrow }\Rightarrow \forall \chi \supseteq \psi \colon \Theta (\chi )(x){\downarrow }=\Theta (\psi )(x)$.
• Kompaktheit: $\Theta (\psi )(x){\downarrow }\Rightarrow \exists \sigma \subset _{\text{fin}}\psi \colon \Theta (\sigma )(x){\downarrow }=\Theta (\psi )(x)$.
• Stetigkeit: $\textstyle \Theta (\psi )=\bigcup _{\sigma \subset _{\text{fin}}\psi }\Theta (\sigma )$.

Eigentlich sind Kompaktheit und Stetigkeit zwei Formulierungen derselben Eigenschaft. Der Begriff Kompaktheit stellt dabei auf die Kompaktheitssätze der mathematischen Logik ab. Stetigkeit dagegen weist darauf hin, dass berechenbare Operatoren tatsächlich als Abbildungen stetig sind, wenn man ${\mathfrak {P}}$ mit der Topologie versieht, die durch die Basismengen $\{\psi \in {\mathfrak {P}}|\sigma _{i}\subset _{\text{fin}}\psi \}_{i\in \mathbb {N} }$ erzeugt wird.

Operator-Rekursionssatz

→ Hauptartikel: Rekursionssatz

Das fundamentale Theorem über berechenbare Operatoren ist der Operator-Rekursionssatz von John Case:

Für jeden berechenbaren Operator $\Theta$ existiert eine total berechenbare Funktion $e\in {\mathcal {R}}$ streng monoton wachsend, so dass gilt: $\forall p;x\colon \varphi _{e(p)}(x)=\Theta (e)(p;x)$.

Der Satz liefert anschaulich gesprochen unendlich viele Programme $e(p)$ berechenbarer Funktionen, die sich allesamt ihrer selbst und der durch $\Theta$ beschriebenen Transformation gewahr sind.

Aufzählbare Reduktion

→ Hauptartikel: Aufzählbare Reduktion

Seien $\psi ;\chi \in {\mathfrak {P}}$ partielle Funktionen.

• Die Abbildung $\chi$ heiße aufzählbar reduzierbar auf (engl.: enumeration reducible to) bzw. partiell berechenbar in $\psi$, $\chi \preceq _{e}\psi$, falls es einen berechenbaren Operator $\Theta$ gibt, so dass $\Theta (\psi )=\chi$.

Die Reduktion $\preceq _{e}$ definiert eine Präordnung auf der Menge ${\mathfrak {P}}$, insbesondere ist die Relation transitiv. Für je zwei berechenbare Funktionen $f;g\in {\mathcal {P}}$ gilt dabei $f\equiv _{e}g$, außerdem gibt es in ${\mathfrak {P}}$ keine Funktion die bzgl. $\preceq _{e}$ echt unter der Klasse ${\mathcal {P}}$ der berechenbaren Abbildungen liegt. Beides lässt sich leicht mittels konstanter Operatoren (s. o.) zeigen.

Für total berechenbare Abbildungen $f;g\in {\mathcal {R}}$ gilt sogar, dass $f$ genau dann berechenbar in $g$ ist, wenn der Graph von $f$ (als Menge natürlicher Zahlen) Turing-reduzierbar auf den Graphen von $g$ ist, $f\preceq _{e}g\Leftrightarrow f\preceq _{T}g$. Im Allgemeinen ist die aufzählbare Reduktion aber mit der Turing-Reduktion unvergleichbar.

Quellen

• John W. Case: Periodicity in Generations of Automata. In: Mathematical Systems Theory. 8. Jahrgang, Nr. 1. Springer-Verlag, 1974, S. 15–32, doi:10.1007/BF01761704. 
• Sharma Jain et al.: Systems That Learn. 2nd Auflage. MIT Press, Cambridge, Massachusetts 1999, ISBN 0-262-10077-0, S. 19. 
• Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1987, ISBN 0-262-68052-1, S. 145–149.