משפט הרקורסיה

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

משפט הרקורסיה (גם: משפט נקודת השבת, או משפט הרקורסיה של קליני) הוא משפט בתורת החישוביות הנוגע לקשר בין פונקציות בנות־חישוב לתיאור שלהן. המשפט הוכח על ידי סטיבן קליני בשנת 1938. המשפט מדגים כי לכל פונקציה בת־חישוב ניתן לבנות פונקציה "דומה" בעלת נקודת שבת מסוימת. השלכות המשפט מאפשרות הוכחת אי־כריעות של שפות מסוימות (למשל, אי־כריעות בעיית העצירה), וכן הוכחת משפטי האי שלמות של גדל.


P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0