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.