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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم بين الحرمين يقدم ورشة تدريبية عن صيانة العجلات الكهربائية للملاكات الفنية في مدينة الفردوس

مجموعة مشاتل الكفيل تستقبل طلبة مجموعة العميد التربوية

قسم العلاقات العامة ينظم محاضرة ثقافية لوفد مركز الزهراء (عليها السلام) من ألمانيا

المجمع العلمي يحيي ذكرى ولادة الإمام علي (عليه السلام) في كربلاء

المزيد

الآخبار الصحية

طبيب يكشف أفضل مكمل غذائي لتحسين المزاج ودعم الصحة النفسية

دراسة جديدة تكشف أضرار الأطعمة الجاهزة على القلب ؟

6 أطعمة طبيعية تهدئ الزكام دون أدوية.. تعرف عليهم

ماذا يحدث لأعراض الزكام عند تناول الثوم بانتظام؟

المزيد

الآخبار التكنلوجية

ابتكار ثوري في بطاريات السيارات الكهربائية.. سعة أعلى 4 مرات

ماذا يحدث لجسمك عند شرب الماء الساخن يوميا؟

7 فوائد "خفية" لشرب شاي الكركديه كل يوم

دراسة تكشف قدرة الحيتان على سماع الأصوات منخفضة وعالية التردد من مسافة بعيدة

المزيد

مواضيع ذات صلة

Lemma

Proof

Zeno,s Paradoxes

Unexpected Hanging Paradox

Strange Loop

Sorites Paradox

Simpson,s Paradox

Russell,s Antinomy

Paradox

Newcomb,s Paradox

Missing Dollar Paradox

Line Point Picking