Die Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene, Rogers und Case. 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 und erschien 1952 in dessen Introduction to Metamathematics. 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.

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. Es zeigte sich schnell, dass der Satz sogar äquivalent zur ursprünglichen Aussage ist.

Operator-Rekursionssatz

Der Operator-Rekursionssatz (engl.: operator recursion theorem, ORT) von John Case aus dem Jahre 1974 behandelt eine scheinbar allgemeinere Fassung der oben angegebenen Rekursionssätze. Er beschreibt dabei eine Eigenschaft berechenbarer Operatoren, das sind Abbildungen ${\displaystyle \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 ${\displaystyle \Theta }$ existiert eine total berechenbare Funktion ${\displaystyle e\in {\mathcal {R}}}$ streng monoton wachsend, so dass gilt ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle f\in {\mathcal {P}}}$, die genau dann für Eingabe ${\displaystyle (p;x)}$ hält (definiert ist), wenn ${\displaystyle \varphi _{p}(x){\uparrow }}$ nicht hält. Aus dem Rekursionssatz von Kleene folgt nun die Existenz eines Programmes ${\displaystyle e}$, so dass ${\displaystyle \varphi _{e}(x)=f(e;x)}$. Insgesamt also ${\displaystyle \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

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