Kleene,s Recursion Theorem
المؤلف:
Davis, M
المصدر:
Computability and Unsolvability. New York: Dover, 1982.
الجزء والصفحة:
...
18-1-2022
1134
Kleene's Recursion Theorem
Let 
denote the recursive function of 
variables with Gödel number 
, where (1) is normally omitted. Then if 
is a partial recursive function, there exists an integer 
such that
where 
is Church's lambda notation. This is the variant most commonly known as Kleene's recursion theorem.
Another variant generalizes the first variant by parameterization, and is the strongest form of the recursion theorem. This form states that for each 
, there exists a recursive function 
of 
variables such that 
is a injection and if 
is a total function, then for all 
, ..., 
, and 
,
Yet another and weaker variant of the recursion theorem guarantees the existence of a recursive function that is a fixed point for a recursive functional.
REFERENCES
Davis, M. Computability and Unsolvability. New York: Dover, 1982.
Kleene, S. C. Introduction to Metamathematics. Princeton, NJ: Van Nostrand, 1964.
Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.
الاكثر قراءة في المنطق
اخر الاخبار
اخبار العتبة العباسية المقدسة
