תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירה |
אין תקציר עריכה |
||
שורה 1:
בפרק זה נעסוק ב'''משפט הרקורסיה''' – אחד המשפטים המעניינים והמפתיעים שקיימים. פרק זה יהיה מעט פילוסופי, וקצת יסטה מהקו הפורמלי שנקטנו בו עד כה, מכיוון שהמטרה היא להביע את הרעיון ולא את "הפרטים הקטנים" שעומדים מאחריו. הרעיון העיקרי של הפרק הוא רעיון ה{{וק|הפניה עצמית|הפניה העצמית}} בו מ״ט מתייחסת לעצמה, או לקוד של עצמה.
==תוכניות המייצרות את עצמן==
תחילתו של פרק זה בשאלה "האם קיימת תוכנית שמדפיסה את הקוד של עצמה". חשוב על כך מעט. האם אתה מסוגל לכתוב תוכנית, בשפת C, פסקל או אפילו שפת סקריפט כלשהי (Rubi, Perl, ect.{{D}}), שהפעתה תדפיס למסך, באופן מדוייק, את הקוד של התוכנית שלך?
{{אתגר|נסה לכתוב תוכנית בשפת C, שמדפיסה את הקוד של עצמה. כלומר, אם קוד התוכנית הוא self.c, ברגע שנפעיל את התוכנית 'self' הפלט למסך יהיה זהה לתוכן הקובץ self.c. ניתן להשתמש בכל שפת תכנות רצוייה.}}
אם ניסית לפתור את האתגר, וודאי שמת לב שקיים קושי ממשי בכתיבת תוכנה זו: בכל פעם שאנחנו רוצים לשנות את הפלט כדי שיהיה זהה לקוד הנוכחי, הדבר משנה את הקוד הנוכחי.. זו מין לולאה כזו שקשה לתפוס בשני הקצוות שלה. למרבה ההפתעה, ניתן לכתוב תוכנות כאלו (השם באנגלית הוא quine), ובאינטרנט קיימות מספר רב של דוגמאות (למשל [http://www.nyx.net/~gthompso/quine.htm the Quine Page])
===לקראת בניית תוכנית-מייצרת-עצמה===
ננסה להסביר את הקושי בכתיבה של תוכנית כנ״ל. הדוגמאות שלהלן יהיו ב{{וק|פסאודו קוד}} לשם הנוחות אבל אפשר לחשוב על תירגומן לכל שפת תכנות שהיא. נניח להלן שטקסט המצוי בתוך מרכאות (לדוגמא: "טקסט") מסמל מחרוזת שכתובה למשל על סרט הזיכרון. טקסט ללא מרכאות מסמל את פעולת התוכנה (למשל, ע״י מצבים מתאימים במכונת־טיורינג).
פתרון ראשון, וודאי נראה כך:
<code>
הדפס כפלט את המחרוזת הבאה:
:"הדפס כפלט את המחרוזת הבאה:".
</code>
האם הפתרון הזה מספק? אם נתעלם לרגע מפרטים קטנים כגון הדפסת הנקודה בסוף משפט והדפסת סימני המרכאות, קל לראות שהפלט לא זהה למקור, מכיוון שהפלט יהיה
הדפס כפלט את המחרוזת הבאה:
כלומר, רק הפקודה, ללא הטקסט שלאחריה. אם כך, נרצה לשנות את התוכנית שלנו, כך שתדפיס את המחרוזת '''פעמיים''': פעם "נקי" ופעם בתוך מרכאות. תוכנית לדוגמא, תראה כך:{{ש}}
<code>
הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות:
:"הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות".
</code>
==לקריאה נוספת==
* [[w:en:Quine (computing)|Quine (computing)]]{{D}}, ויקיפדיה באנגלית.
[[קטגוריה:תורת החישוביות]]
| |||