תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←מכונת־טיורניג מייצרת עצמה: תיקון |
מ ←משפט הרקורסיה: בדוגמאות הקידוד מופיע לפני הקלט |
||
שורה 64:
{{משפט|שם=משפט הרקורסיה|תוכן=לכל מ״ט <math>M</math> קיימת מ״ט <math>M^*</math> כך שמתקיים:
#<math>L(M) = L(M^*)</math>, כלומר, <math>M</math> ו־<math>M^*</math> מכריעות את אותה השפה (מחשבות את אותה הפונקציה)
# <math>M^*</math> יודעת את הקידוד של עצמה, כלומר, עם הפעלתהּ, <math>M^*</math> רושמת את <math>\langle M^* \rangle</math> על סרט הזיכרון (נניח,
| |||