תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף

בפרק זה נעסוק ב'''משפט הרקורסיה''' – אחד המשפטים המעניינים והמפתיעים שקיימים, ולו שימושים רבים ב{{וק[[w:חישוביות|חישוביות}}]], {{וק|[[w:לוגיקה מתמטית|לוגיקה}}]] ו{{וק[[w:תורת הקבוצות|תורת הקבוצות}}]]. פרק זה יהיה מעט פילוסופי, וקצת יסטה מהקו הפורמלי שנקטנו בו עד כה, מכיוון שהמטרה היא להביע את הרעיון ולא את "הפרטים הקטנים" שעומדים מאחריו. הרעיון העיקרי של הפרק הוא רעיון ה{{וק|[[w:הפניה עצמית|הפניה העצמית}}]] בו מ״ט מתייחסת לעצמה, או לקוד של עצמה.

ננסה להסביר את הקושי בכתיבה של תוכנית כנ״ל. הדוגמאות שלהלן יהיו ב{{וק[[w:פסאודו קוד|פסאודו קוד}}]] לשם הנוחות אבל אפשר לחשוב על תירגומן לכל שפת תכנות שהיא. נניח להלן שטקסט המצוי בתוך מרכאות (לדוגמא: "טקסט") מסמל מחרוזת שכתובה למשל על סרט הזיכרון. טקסט ללא מרכאות מסמל את פעולת התוכנה (למשל, ע״י מצבים מתאימים במכונת־טיורינג).