תורת החישוביות/משפט הרקורסיה

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

בפרק זה נעסוק במשפט הרקורסיה – אחד המשפטים המעניינים והמפתיעים שקיימים, ולו שימושים רבים בחישוביות, לוגיקה ותורת הקבוצות. פרק זה יהיה מעט פילוסופי, וקצת יסטה מהקו הפורמלי שנקטנו בו עד כה, מכיוון שהמטרה היא להביע את הרעיון ולא את "הפרטים הקטנים" שעומדים מאחריו. הרעיון העיקרי של הפרק הוא רעיון ההפניה העצמית בו מ״ט מתייחסת לעצמה, או לקוד של עצמה.

תוכניות המייצרות את עצמן[עריכה]

תחילתו של פרק זה בשאלה "האם קיימת תוכנית שמדפיסה את הקוד של עצמה". חשוב על כך מעט. האם אתה מסוגל לכתוב תוכנית, בשפת C, פסקל או אפילו שפת סקריפט כלשהי (Rubi, Perl, etc.‎), שהפעלתה תדפיס למסך, באופן מדוייק, את הקוד של התוכנית שלך?


אתגר:

נסה לכתוב תוכנית בשפת C, שמדפיסה את הקוד של עצמה. כלומר, אם קוד התוכנית הוא self.c, ברגע שנפעיל את התוכנית 'self' הפלט למסך יהיה זהה לתוכן הקובץ self.c. ניתן להשתמש בכל שפת תכנות רצוייה.

אם ניסית לפתור את האתגר, וודאי שמת לב שקיים קושי ממשי בכתיבת תוכנה זו: בכל פעם שאנחנו רוצים לשנות את הפלט כדי שיהיה זהה לקוד הנוכחי, הדבר משנה את הקוד הנוכחי.. זו מין לולאה כזו שקשה לתפוס בשני הקצוות שלה. למרבה ההפתעה, ניתן לכתוב תוכנות כאלו (השם באנגלית הוא quine), ובאינטרנט קיימות מספר רב של דוגמאות (למשל the Quine Page)

לקראת בניית תוכנית-מייצרת-עצמה[עריכה]

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

פתרון ראשון, וודאי נראה כך:

הדפס כפלט את המחרוזת הבאה:

"הדפס כפלט את המחרוזת הבאה:".

האם הפתרון הזה מספק? אם נתעלם לרגע מפרטים קטנים כגון הדפסת הנקודה בסוף משפט והדפסת סימני המרכאות, קל לראות שהפלט לא זהה למקור, מכיוון שהפלט יהיה

הדפס כפלט את המחרוזת הבאה:

כלומר, רק הפקודה, ללא הטקסט שלאחריה. אם כך, נרצה לשנות את התוכנית שלנו, כך שתדפיס את המחרוזת פעמיים: פעם "נקי" ופעם בתוך מרכאות. תוכנית לדוגמא, תראה כך:
הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות:

"הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות".

כעת ננסה לבצע את אותו רעיון בעזרת מכונות־טיורינג.

מכונת־טיורניג מייצרת עצמה[עריכה]

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

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

נזכיר שלכל מחרוזת קבועה x אנחנו יכולים להגדיר מכונה שכל מה שהיא עושה הוא לכתוב את x על הסרט. מכיוון שהמחרוזת x קבועה, המכונה מוגדרת היטב. למשל, המכונה יכולה להכיל 4 מצבים שכותבים "010" על הסרט ועוצרים את פעולת המכונה. באופן כללי, בעזרת מצבים ניתן לבנות מ״ט כנ״ל לכל מחרוזת נתונה.

האם המכונה היא הפתרון שרצינו? כדי שמכונה זו תהווה את הפתרון, אנחנו בעצם רוצים לבנות את , שמדפיסה את הקידוד של עצמה, . ושוב נתקלנו בלולאה העצמית, שהרי הקידוד של תלוי בפלט שהיא כותבת, ואם זו אינה מחרוזת קבועה x, אנחנו בבעיה.

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

  • הראשונה: יצירת המחרוזת x על הסרט (בפסאודו־קוד x="הדפס כפלט את המחרוזת הבאה פעמיים, כאשר הפעם השניה בתוך מרכאות")
  • השנייה: בהינתנן שהמחרוזת x כבר נתונה לנו, צריך לרשום אותה "פעמיים"

הפעולה הראשונה מוסברת ע״י המכונה שהגדרנו (כרגע, עוד בלי לדעת מהו x המתאים). כעת ננסה להגדיר מ״ט שתבצע את הפעולה השניה.

המכונה מתחילה כאשר המחרוזת x כבר קיימת על הסרט. איך x הגיעה לסרט? ע״י המכונה . כלומר, אנחנו בונים בעצם מכונה שקודם מריצה את B ואח"כ את A. נקרא למכונה זו ונסמן לציין שהקידוד של המכונה שמריצה את B ואח״כ את A הוא הקידוד של B ולאחריו הקידוד של A.

הפעולה של מכונה היא פשוטה: היא לוקחת את המחרוזת x וכותבת אותה "פעמים" על הסרט. כלומר, אחרי הרצת המכונה , סרט הזיכרון יכיל את התוכן :

אבל זה לא בדיוק מה שרצינו. הבדל אחד, למשל, הוא שהקידוד של מכיל בהתחלה את ולא את x ישירות. קל לתקן את ההבדל הנ״ל: נשנה את כך שבמקום להדפיס את x פעמיים, תדפיס את (ולאחריו תשאיר את המחרוזת x שכבר נמצאת בזיכרון). כפי שראינו לעיל, אם x היא מחרוזת קבועה אז קל לבנות את : לכל אות ב־x בונים מצב ומעבר מתאים של .

אתגר:

בנה מ״ט שעל הקלט x משנה את סרט הזיכרון כך שיופיע הקידוד של המתאימה  

נריץ את המכונה M שבנינו עד כה ונראה שמתקבל הפלט (מאד דומה למה שרצינו!):

נותר צעד אחרון - להגדיר מהי המחרוזת הקבועה x ?
הפלט שקיבלנו עד כה הוא , ואילו הפלט שאנחנו רוצים הוא . מכאן ברור שהמחרוזת x היא לא אחרת מאשר הקידוד של המכונה A, . נשים לב שזו מחרוזת קבועה, מדובר סה״כ במ״ט שמקבלת קלט כלשהו w וכותבת על הסרט את הקידוד של המכונה עבור אותו פלט שקיבלה. מכונה זו מוגדרת היטב, ויש לה קידוד מסויים שלא קשה להגדיר (ראה אתגר לעיל).

לסיכום, נגדיר מ״ט שמייצרת את הקידוד של עצמה. המכונה על קלט כלשהו w:

  1. מחק את הזיכרון והרץ את
  2. הרץ את המכונה A (על סרט הזיכרון הנוכחי).

לאחר השלב הראשון סרט הזיכרון יכיל את המחרוזת . בשלב השני המכונה A מופעלת על המחרוזת (שזו מבחינתה מחרוזת סתמית לכל דבר), ומייצרת על הסרט את הקידוד , ושמה אותו על הסרט לפני המחרוזת הקיימת שם. בסוף התהליך הסרט יכיל את המחרוזת .

משפט הרקורסיה[עריכה]

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


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

לכל מ״ט קיימת מ״ט כך שמתקיים:

  1. , כלומר, ו־ מכריעות את אותה השפה (מחשבות את אותה הפונקציה)
  2. יודעת את הקידוד של עצמה, כלומר, עם הפעלתהּ, רושמת את על סרט הזיכרון (נניח, מיד לפני הקלט שניתן למכונה)


כעת נוכיח את המשפט. נניח שנתונה מכונה ונראה כיצד לבנות את המכונה בעזרת ובעזרת המכונות שהגדרנו לעיל.

נתחיל בנסיון פשוט לבנות את המכונה: ראשית היא אמורה לכתוב את הקידוד של עצמה על סרט הזיכרון, ולאחר מכן לבצע את הפעולה של M. נבחן את הפתרון , כלומר קודם מריצה את B אח״כ את A ואח״כ את M. לפתרון זה שתי בעיות. ראשית, הפעלת B ואחריו A כותבת על הסרט את הקידוד , ולא את . שנית, אם נפעיל את על הסרט אחרי שכתבנו עליו את הקידוד – התוצאה עלולה להיות לא נכונה, מכיוון ש־ מניחה שכל מה שרשום על הסרט הוא הקלט שלה.

ראשית נפתור את הבעיה השניה. נגדיר מכונה C שמבצעת את אותה פעולה כמו M, אבל "מתעלמת" מהחלק הראשון של הקלט שלה. כלומר, אם הקלט של C הוא , המכונה מריצה את M על המחרוזת בלבד. באופן פורמלי . קל לבנות מכונה כנ״ל מתוך הקידוד של . כעת ברור שאם , והחלק יכתוב את על הסרט (לפני הקלט w שכבר רשום על הסרט בתחילת הריצה!) אז המכונה תחשב את אותה הפונקציה כמו , .

נותר לנו לפתור את הבעיה הראשונה, דהיינו, לגרום לכך שהפעלת המכונות תייצר את הקידוד של . נשים לב שלפי הגדרת הקידוד שלה נתון ע״י . כמו מקודם, נוכל לקבוע את המחרוזת לכל מחרוזת קבועה שנרצה. נקבע ונקבל שלאחר הרצת המכונות , הסרט יכיל את המחרוזת , כאשר הוא הקלט של המכונה:

כעת, הרצת על סרט הזיכרון תחשב את על w, כנדרש.


שימו לב:

בהוכחה הנ"ל קיים אי־דיוק: נצטרך להגדיר את A מחדש כך שהיא מתעלמת מהקלט w. קל לראות שפעולה זו אינה משנה את נכונות ההוכחה

שימושים[עריכה]

משפט הרקורסיה מאפשר לנו להניח שהמ״ט בה אנו מתעניינים, יכולה לגשת לקידוד של עצמה. עובדה זו מאפשר "הפניה עצמית" בצורה קלה ונוחה, ויש לה השלכות רבות.

אי־כריעות[עריכה]

נוכיח, בעזרת משפט הרדוקציה שהשפה אינה כריעה.

הוכחה: נניח, בשלילה, ש־ כריעה והמכונה מכריעה אותה. נבנה מכונה חדשה באופן הבא.
על הקלט :

  1. בעזרת משפט הרדוקציה, כותבת על סרט הזיכרון את .
  2. המכונה מריצה את M על הקלט
    1. אם M מקבלת את הקלט, CONT נכנסת ללולאה אינסופית
    2. אחרת, CONT עוצרת ומקבלת

קל לראות ש־CONT יוצרת סתירה: הגישה לקידוד שלה מאפשר לה לגלות, תוך כדי ריצתה, האם היא אמורה לעצור או לא (בהנחה שבעיה זו כריעה!); CONT מתנהגת באופן הפוך למה שהיא "אמורה" להתנהג, ויוצרת סתירה. פורמלית, עבור מחרוזת w כלשהי,

  • אם , אזי M תקבל את הקלט, ו־ תכנס ללולאה אינסופית על w, בסתירה לכך ש־.
  • אם , אזי M תדחה את הקלט, ו‏־ תעצור ותקבל את w, בסתירה לכך ש־.


מש"ל.PNG

הוכחה זו, במובן מסוים, פשוטה וקלה מההוכחה שראינו בפרק קיום שפות שאינן כריעות.


משפט האי־שלמות של גדל[עריכה]

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

מערכת הוכחה[עריכה]

מערכת הוכחה F היא קבוצה של אקסיומות "Axiom" וקבוצה של כללי היסק לוגיים "Rules". דוגמא לאקסיומה יכולה להיות "היום יום ראשון". ודוגמא לכלל היסק לוגי יכול להיות "אם טענה A גוררת את טענה B, וגם ידוע ש־A טענה נכונה, אז גם B טענה נכונה" (מודוס פוננס).

  • אנחנו אומרים שניתן להוכיח את הטענה ע״י המערכת F אם היא אקסיומה בעצמה, או אם ניתן להסיק את הטענה S מתוך האקסיומות וכללי ההיסק. מסמנים (S יכיחה ב־F).
  • הוכחה היא למעשה מחרוזת שמסבירה איך מסיקים את S מתוך האקסיומות וכללי ההיסק. (הוכחה סתמית לדוגמא יכולה להראות כך: "קח את האקסיומה הראשונה והשניה, הפעל עליהם את כלל ההיסק השלישי ותקבל טענה . הפעל את כלל ההיסק החמישי על ותקבל טענה . הפעל את כלל ההיסק השלישי על ועל האקסיומה החמישית, ותקבל את ")
  • חשוב לציין שבהנתן טענה (מחרוזת S) והוכחה (מחרוזת x) קל לוודא האם x היא הוכחה ל־S. כלומר קיימת מ״ט שעל קלט עוצרת ועונה כן/לא בהתאם להאם x היא הוכחה של S.

נאמר שמערכת F היא:

  1. עקבית: כאשר לא קיימת טענה S כך ש־ וגם
  2. שלמה: אם לכל טענה S, או ש־ או ש־

משמעות העקביות היא שלא ניתן להוכיח טענות "שגויות". אם ניתן להוכיח טענה וגם היפוכה, המערכת מאבדת את ההגיון שבה, כי ניתן להוכיח בעזרה ששקר(False) הוא טענת-אמת (), ומכאן ניתן להוכיח כל טענה (כי הוא טענת אמת).

משמעות השלמות היא שכל טענה היא או "נכונה" או "שקרית" כלומר, ניתן להוכיח אותה, או להוכיח את שלילתה.



משפט: משפט האי-שלמות הראשון של גדל

לכל מערכת הוכחה F חזקה דיו ועקבית, F אינה שלמה.     


הוכחת משפט גדל בעזרת משפט הרקורסיה[עריכה]

כעת נניח שיש לנו מערכת הוכחה F "חזקה דיו" במובן שניתן לתאר בה טענות לגבי מכונות טיורינג. בפרט, נניח שניתן לתאר בה את תהליך החישוב של מכונת טיורינג, ולנסח טענות שאומרות "המכונה M עוצרת".

Blue think.svg המערכת שאנו משתמשים בה ביום יום (באופן מובלע) נקראת ZFC, והיא חזקה דיו לתאר מ״ט. למשל טענה לגבי עצירה של מכונה M תהיה בסגנון הבא: קיימת סדרה כך שמתקיים (1) היא קונפיגורציה תחילתית של M (על קלט ריק); (2) לכל הקונפיגורציה היא הקונפיגורציה העוקבת של ; (3) היא קונפיגורציה סופית

כעת נגדיר את המכונה הבאה M:

  1. בעזרת משפט הרקורסיה, M משיגה את הקידוד שלה
  2. בעזרת המכונה מגדירה את הטענה (המחרוזת) S
    S: "המכונה לא עוצרת על הקלט הריק"
  3. המכונה מונה את כל המחרוזות x (ההוכחות x), אחת אחרי השניה. עבור כל מחרוזת:
    1. המכונה בודקת האם x היא הוכחה של הטענה S במערכת F.
    2. אם כן, המכונה עוצרת.

כעת, נוכיח את משפט גדל. נניח בשלילה, שהמשפט שגוי, כלומר F היא גם עקבית וגם שלמה. נבצע חלוקה למקרים:

  • : כלומר יש הוכחה ב־F לטענה S. אחרי זמן סופי M תמצא את ההוכחה, ותעצור. אבל אם הטענה S נכונה (הרי, מצאנו עבורה הוכחה!) הרי ש־M אינה עוצרת. מאידך יש לנו הוכחה שהיא כן עוצרת: סדרת הקונפיגורציות שמוצאת את היא הוכחה ש־M כן עוצרת. במילים אחרות יש לנו שתי הוכחות: אחת של הטענה ש־M לא עוצרת, והשניה של הטענה ש־M כן עוצרת. הוכחנו טענה ושלילתה F לא עקבית! בסתירה להנחה.
  • : כלומר יש הוכחה לכך ש־M עוצרת. מכיוון שהנחנו ש־F עקבית, לא ייתכן שקיימת הוכחה לכך ש־M כן עוצרת, כלומר, לא קיימת הוכחה ל־S. מכיוון שכך, המכונה M לעולם לא תעצור (כי לא קיים x שיגרום לא לעצור), אבל זו הרי סתירה לכך ש היא טענת-אמת (שהרי, הוכחנו אותה!).

נובע שהטענה S היא עצמה טענה שאין ב־F הוכחה עבורה, וגם אין ב־F הוכחה עבור הטענה ההפכית , ומכאן ש־F אינה שלמה.

לקריאה נוספת[עריכה]

  • Quine (computing)‎, ויקיפדיה באנגלית.
  • דאגלס הופשטטר, Gödel, Escher, Bach: an Eternal Golden Braid‏ , 1979.


הפרק הקודם:
אי-הפרדתיות רקורסיבית
משפט הרקורסיה הפרק הבא:
סיבוכיות קולמוגורוב