Rekursionssatz

Die Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene^[1], Rogers^[2] und Case^[3]. Sie beschreiben selbstreferenzielle Eigenschaften berechenbarer Funktionen. Dies wird durch algorithmische Modifikation natürlicher Zahlen erreicht, die einerseits als Codierungen von Programm-Quelltexten und andererseits als Funktionsargumente dienen. Trotz der sehr unterschiedlich gelagerten Aussagen sind alle drei Sätze formal äquivalent, aus jedem von ihnen lassen sich die jeweils anderen beiden herleiten. Die Rekursionssätze folgen allesamt aus dem Smn-Theorem, das ebenfalls zuerst von Kleene bewiesen wurde.

Rekursionssatz von Kleene

Der Rekursionssatz von Kleene (engl.: Kleene's recursion theorem, KRT) wurde bereits 1938 von Stephen Cole Kleene bewiesen^[1] und erschien 1952 in dessen Introduction to Metamathematics^[4]. Diese Fassung begründet auch die Bezeichnung als Rekursionsatz, da sie sich ursprünglich auf ein rekursiv definiertes Notationssystem für Ordinalzahlen bezog, lange bevor in der Berechenbarkeitstheorie rekursiv ein Synonym für berechenbar wurde.

Nicht-konstruktive Fassung

Sei

\{\varphi _{p}\}_{p\in \mathbb {N} }

eine effektive Nummerierung aller partiell berechenbaren Funktionen (bspw. die Gödel-Nummerierung aller deterministischen Turing-Maschinen).

Für jede partiell berechenbare Funktion $f\in {\mathcal {P}}$ existiert dann ein Index $e\in \mathbb {N}$ , so dass $\forall x\in \mathbb {N} \colon \varphi _{e}(x)=f(e;x)$ .

Konstruktive Fassung

Tatsächlich gibt es sogar eine total berechenbare Funktion $e\in {\mathcal {R}}$ streng monoton wachsend, so dass gilt $\forall p;x\in \mathbb {N} \colon \varphi _{e(p)}(x)=\varphi _{p}(e(p);x)$ .

Für jede mögliche Berechnung $f$ gibt es also ein Programm $e$ , das diese Berechnung auf dem eigenen Quelltext ausführt. Eine Codierung dieses selbstreferenziellen Programmes lässt sich sogar effektiv aus einem Index $p$ für die gewünschte Berechnung bestimmen. Die nicht-konstruktive Fassung folgt also aus der konstruktiven durch die Setzung $f=\varphi _{p}$ .

Fixpunktsatz von Kleene

Der Fixpunktsatz von Kleene (engl. häufig: Rogers' fixed-point theorem) ist eine einfachere Version des oben stehenden Rekursionssatzes, die 1967 von Hartley Rogers jr. angegeben wurde.^[2] Es zeigte sich schnell, dass der Satz sogar äquivalent zur ursprünglichen Aussage ist.^[5]

Nicht-konstruktive Fassung

Für jede total berechenbare Funktion $f\in {\mathcal {R}}$ existiert ein Index $e\in \mathbb {N}$ , so dass $\forall x\in \mathbb {N} \colon \varphi _{e}(x)=\varphi _{f(e)}(x)$ .

Konstruktive Fassung

Mit der zusätzlichen Setzung

\varphi _{f(e)}=\bot

, falls

f(e)=\bot

, lässt sich die Aussage auch auf partielles

f\in {\mathcal {P}}

verallgemeinern.

In diesem Fall gibt es dann erneut eine total berechenbare Funktion $e\in {\mathcal {R}}$ streng monoton wachsend, so dass gilt $\forall p;x\in \mathbb {N} \colon \varphi _{e(p)}(x)=\varphi _{\varphi _{p}(e(p))}(x)$ .

Der Fixpunktsatz besagt also, dass sich zu jeder (berechenbaren) Quelltext-Manipulation ein Programm findet, dem die Modifikation nichts ausmacht. Das heißt, der Quelltext wird zwar modifiziert, dies hat aber für die Funktion des Programms, das durch diesen Quelltext dargestellt wird, keine Auswirkungen. Da sich also die Semantik des Programms nicht ändert, spricht man auch von einem semantischen Fixpunkt der syntaktischen Programmtransformation. Wieder lässt sich ein solcher Fixpunkt effektiv aus einem Index für die betrachtete Manipulation bestimmen. Tatsächlich gibt es für jede Modifikation sogar unendlich viele semantische Fixpunkte.

Operator-Rekursionssatz

Der Operator-Rekursionssatz (engl.: operator recursion theorem, ORT) von John Case aus dem Jahre 1974^[3] behandelt eine scheinbar allgemeinere Fassung der oben angegebenen Rekursionssätze. Er beschreibt dabei eine Eigenschaft berechenbarer Operatoren, das sind Abbildungen $\Theta \colon (\mathbb {N} \rightsquigarrow \mathbb {N} )\to (\mathbb {N} \rightsquigarrow \mathbb {N} )$ zwischen partiellen (nicht notwendigerweise berechenbaren) Funktionen, die durch eine Turing-Maschine realisiert werden.

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

Der wesentliche Unterschied zu der Fassung von Kleene ist, dass ORT nicht nur einen einzigen selbstreferenziellen Index, sondern gleich unendlich viele Gödel-Nummern $e(p)$ liefert, die alle – bildlich gesprochen – ihrer selbst und aller anderen Indizes gewahr sind. Außerdem greift der Operator-Rekursionssatz direkt auf der Ebene berechenbarer Funktionen, während die obigen Versionen Quelltext-Manipulationen behandeln. Tatsächlich folgt aber auch die Fassung von Case aus dem ursprünglichen Rekursionssatz von Kleene und ist damit zu diesem äquivalent.

Anwendungen

Die Rekursionssätze sind eine beliebte Quelle für (Gegen-)Beispiele in der Berechenbarkeitstheorie und der algorithmischen Lerntheorie. Sie werden gerne als Hilfssätze in Beweisen verwendet, wenn man die Existenz einer bestimmten berechenbaren Funktion zeigen will.

Zum Beispiel folgt die Existenz eines Quines – eines Programms, das seinen eigenen Quelltext ausgibt – sehr einfach aus der Fixpunkt-Variante. Dazu definiert man die Modifikatorfunktion so, dass die gesuchte Funktion ein Fixpunkt ist. Im Fall der Quines wäre das bspw. die Funktion, die ein Programm zurückgibt, das den gerade eingegebenen Quelltext ausgibt (Pseudocode):

f(x): return "return " + x

Der Fixpunkt ist dann ein Quine.

Umgekehrt lässt sich durch die Rekursionssätze auch die Nicht-Berechenbarkeit bestimmter Funktionen zeigen. Dazu nimmt man an, die betrachtete Abbildung sei doch berechenbar, dann ist durch sie eine Quelltext-Manipulation oder ein berechenbarer Operator erklärt. Die daraus folgende Existenz selbstreferenzieller Indizes oder Funktionen kann dann genutzt werden, um einen Widerspruch zu konstruieren.

So liefert der Rekursionssatz von Kleene einen alternativen Beweis für die Unentscheidbarkeit des Halteproblems $H=\{(p;x)|\varphi _{p}(x){\downarrow }\}$ : Angenommen es sei doch entscheidbar, dann ist sein Komplement rekursiv aufzählbar. Das heißt, es gibt eine partiell berechenbare Funktion $f\in {\mathcal {P}}$ , die genau dann für Eingabe $(p;x)$ hält (definiert ist), wenn $\varphi _{p}(x){\uparrow }$ nicht hält. Aus dem Rekursionssatz von Kleene folgt nun die Existenz eines Programmes $e$ , so dass $\varphi _{e}(x)=f(e;x)$ . Insgesamt also $\varphi _{e}(x){\uparrow }\Leftrightarrow f(e;x){\downarrow }\Leftrightarrow \varphi _{e}(x){\downarrow }$ , ein Widerspruch.

Siehe auch

Liste von Sätzen der Informatik

Literatur

Robert I. Soare: Recursively Enumerable Sets and Degrees. Springer, Berlin 1987. ISBN 0387152997
Christos H. Papadimitriou: Computational Complexity. Addison-Wesley Publishing Company, 1994. ISBN 0-201-53082-1

Einzelnachweise

↑ ^a ^b Stephen C. Kleene: On Notation for Ordinal Numbers. In: The Journal of Symbolic Logic. 3. Jahrgang, 1938, S. 150–155 (thatmarcusfamily.org [PDF]).
↑ ^a ^b Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1967, ISBN 0-262-68052-1, S. 179.
↑ ^a ^b 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.
↑ Stephen C. Kleene: Introduction to Metamathematics. North-Holland Publishing Company, New York City, New York 1952, S. 352–353.
↑ Neil D. Jones: Computability and Complexity from a Programming Perspective. MIT Press, Cambridge, Massachusetts 1997.

[Kleene1938-1] Stephen C. Kleene: On Notation for Ordinal Numbers. In: The Journal of Symbolic Logic. 3. Jahrgang, 1938, S. 150–155 (thatmarcusfamily.org [PDF]).

[Rogers1967-2] Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1967, ISBN 0-262-68052-1, S. 179.

[Case1974-3] 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.

[Kleene1952-4] Stephen C. Kleene: Introduction to Metamathematics. North-Holland Publishing Company, New York City, New York 1952, S. 352–353.

[Jones1997-5] Neil D. Jones: Computability and Complexity from a Programming Perspective. MIT Press, Cambridge, Massachusetts 1997.

[1]

[2]

[3]

[4]

[5]