Rekursionssatz

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.

  1. ↑ Stephen C. Kleene: On Notation for Ordinal Numbers. In: The Journal of Symbolic Logic. 3. Jahrgang, 1938, S. 150–155 (englisch, thatmarcusfamily.org [PDF]).
  2. ↑ Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1967, ISBN 0-262-68052-1, S. 179 (englisch).
  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 (englisch).
Dieser Artikel wurde von Wikipedia herausgegeben. Der Text ist unter Creative Commons Attribution-Share Alike 4.0 verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.