Back Kleene's recursion theorem English Théorème de récursion de Kleene French משפט הרקורסיה HE Teorema di ricorsione di Kleene Italian クリーネの再帰定理 Japanese Theoremata Kleene de puncto immobili Latin Teorema da recursividade de Kleene Portuguese ทฤษฎีบทเวียนบังเกิดของคลีน Thai
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.
- ↑ Stephen C. Kleene: On Notation for Ordinal Numbers. In: The Journal of Symbolic Logic. 3. Jahrgang, 1938, S. 150–155 (thatmarcusfamily.org [PDF]). Vorlage:Cite journal: Der Parameter language wurde bei wahrscheinlich fremdsprachiger Quelle nicht angegeben.
- ↑ Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, Cambridge, Massachusetts 1967, ISBN 0-262-68052-1, S. 179. Vorlage:Cite book: Der Parameter language wurde bei wahrscheinlich fremdsprachiger Quelle nicht angegeben.
- ↑ 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. Vorlage:Cite journal: Der Parameter language wurde bei wahrscheinlich fremdsprachiger Quelle nicht angegeben.