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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

נזכיר שלכל מחרוזת קבועה x אנחנו יכולים להגדיר מכונה $B_{x}$ שכל מה שהיא עושה הוא לכתוב את x על הסרט. מכיוון שהמחרוזת x קבועה, המכונה מוגדרת היטב. למשל, המכונה $B_{010}$ יכולה להכיל 4 מצבים שכותבים "010" על הסרט ועוצרים את פעולת המכונה. באופן כללי, בעזרת $Q=|x|+1$ מצבים ניתן לבנות מ״ט כנ״ל לכל מחרוזת $x$ נתונה.

האם המכונה $B$ היא הפתרון שרצינו? כדי שמכונה זו תהווה את הפתרון, אנחנו בעצם רוצים לבנות את $B_{\langle B\rangle }$, שמדפיסה את הקידוד של עצמה, $\langle B\rangle$. ושוב נתקלנו בלולאה העצמית, שהרי הקידוד של $B$ תלוי בפלט שהיא כותבת, ואם זו אינה מחרוזת קבועה x, אנחנו בבעיה.

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

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

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

המכונה $A$ מתחילה כאשר המחרוזת x כבר קיימת על הסרט. איך x הגיעה לסרט? ע״י המכונה $B_{x}$. כלומר, אנחנו בונים בעצם מכונה שקודם מריצה את B ואח"כ את A. נקרא למכונה זו $M$ ונסמן $\langle M\rangle =\langle B_{x}\rangle \langle A\rangle$ לציין שהקידוד של המכונה שמריצה את B ואח״כ את A הוא הקידוד של B ולאחריו הקידוד של A.

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

$(empty)\;{\stackrel {B_{x}}{\Longrightarrow }}\;x\;{\stackrel {A}{\Longrightarrow }}\;xx$

אבל זה לא בדיוק מה שרצינו. הבדל אחד, למשל, הוא שהקידוד של $M$ מכיל בהתחלה את $\langle B_{x}\rangle$ ולא את x ישירות. קל לתקן את ההבדל הנ״ל: נשנה את $A$ כך שבמקום להדפיס את x פעמיים, תדפיס את $B_{x}$ (ולאחריו תשאיר את המחרוזת x שכבר נמצאת בזיכרון). כפי שראינו לעיל, אם x היא מחרוזת קבועה אז קל לבנות את $B_{x}$: לכל אות ב־x בונים מצב ומעבר מתאים של $B_{x}$.

אתגר: בנה מ״ט שעל הקלט x משנה את סרט הזיכרון כך שיופיע הקידוד של $B_{x}$ המתאימה

נריץ את המכונה M שבנינו עד כה ונראה שמתקבל הפלט $\langle B_{x}\rangle \ x$ (מאד דומה למה שרצינו!):

$(empty)\;{\stackrel {B_{x}}{\Longrightarrow }}\;x\;{\stackrel {A}{\Longrightarrow }}\;\langle B_{x}\rangle x$

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

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

1. מחק את הזיכרון והרץ את $B_{\langle A\rangle }$
2. הרץ את המכונה A (על סרט הזיכרון הנוכחי).

לאחר השלב הראשון סרט הזיכרון יכיל את המחרוזת $\langle A\rangle$. בשלב השני המכונה A מופעלת על המחרוזת $\langle A\rangle$ (שזו מבחינתה מחרוזת סתמית לכל דבר), ומייצרת על הסרט את הקידוד $B_{\langle A\rangle }$, ושמה אותו על הסרט לפני המחרוזת הקיימת שם. בסוף התהליך הסרט יכיל את המחרוזת $\langle B_{\langle A\rangle }\rangle \langle A\rangle =\langle M\rangle$.

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

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

משפט: משפט הרקורסיה לכל מ״ט $M$ קיימת מ״ט $M^{*}$ כך שמתקיים: $L(M)=L(M^{*})$, כלומר, $M$ ו־$M^{*}$ מכריעות את אותה השפה (מחשבות את אותה הפונקציה) $M^{*}$ יודעת את הקידוד של עצמה, כלומר, עם הפעלתהּ, $M^{*}$ רושמת את $\langle M^{*}\rangle$ על סרט הזיכרון (נניח, מיד לפני הקלט שניתן למכונה)

כעת נוכיח את המשפט. נניח שנתונה מכונה $M$ ונראה כיצד לבנות את המכונה $M^{*}$ בעזרת $M$ ובעזרת המכונות $A,B$ שהגדרנו לעיל.

נתחיל בנסיון פשוט לבנות את המכונה: ראשית היא אמורה לכתוב את הקידוד של עצמה על סרט הזיכרון, ולאחר מכן לבצע את הפעולה של M. נבחן את הפתרון $M^{*}=B_{x}AM$, כלומר קודם מריצה את B אח״כ את A ואח״כ את M. לפתרון זה שתי בעיות. ראשית, הפעלת B ואחריו A כותבת על הסרט את הקידוד $\langle B\rangle \langle A\rangle$, ולא את $\langle M^{*}\rangle$. שנית, אם נפעיל את $M$ על הסרט אחרי שכתבנו עליו את הקידוד – התוצאה עלולה להיות לא נכונה, מכיוון ש־$M$ מניחה שכל מה שרשום על הסרט הוא הקלט שלה.

ראשית נפתור את הבעיה השניה. נגדיר מכונה C שמבצעת את אותה פעולה כמו M, אבל "מתעלמת" מהחלק הראשון של הקלט שלה. כלומר, אם הקלט של C הוא $(x,y)$, המכונה מריצה את M על המחרוזת $y$ בלבד. באופן פורמלי $C(x,y)=M(y)$. קל לבנות מכונה כנ״ל מתוך הקידוד של $M$. כעת ברור שאם $M^{*}=BAC$, והחלק $BA$ יכתוב את $\langle M^{*}\rangle$ על הסרט (לפני הקלט w שכבר רשום על הסרט בתחילת הריצה!) אז המכונה $M^{*}$ תחשב את אותה הפונקציה כמו $M$, $L(M)=L(M^{*})$.

נותר לנו לפתור את הבעיה הראשונה, דהיינו, לגרום לכך שהפעלת המכונות $BA$ תייצר את הקידוד של $M^{*}$. נשים לב שלפי הגדרת $M^{*}$ הקידוד שלה נתון ע״י $\langle M^{*}\rangle =\langle B_{x}\rangle \langle A\rangle \langle C\rangle$. כמו מקודם, נוכל לקבוע את המחרוזת $x$ לכל מחרוזת קבועה שנרצה. נקבע $x=\langle A\rangle \langle C\rangle$ ונקבל שלאחר הרצת המכונות $B_{\langle A\rangle \langle C\rangle }A$, הסרט יכיל את המחרוזת $\langle B_{\langle A\rangle \langle C\rangle }\rangle \langle A\rangle \langle C\rangle ,w$, כאשר $w$ הוא הקלט של המכונה:

$w\;{\stackrel {B_{\langle A\rangle \langle C\rangle }}{\Longrightarrow }}\;\langle A\rangle \langle C\rangle ,w\;{\stackrel {A}{\Longrightarrow }}\;\langle B_{\langle A\rangle \langle C\rangle }\rangle \langle A\rangle \langle C\rangle ,w$

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

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

שימושים

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

אי־כריעות

נוכיח, בעזרת משפט הרדוקציה שהשפה $L_{\text{HP}}$ אינה כריעה.

הוכחה: נניח, בשלילה, ש־$L_{\text{HP}}$ כריעה והמכונה $M$ מכריעה אותה. נבנה מכונה חדשה $CONT$ באופן הבא.
$CONT$ על הקלט $w$:

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

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

• אם $(\langle CONT\rangle ,w)\in L_{\text{HP}}$, אזי M תקבל את הקלט, ו־$CONT$ תכנס ללולאה אינסופית על w, בסתירה לכך ש־$(\langle CONT\rangle ,w)\in L_{\text{HP}}$.
• אם $(\langle CONT\rangle ,w)\notin L_{\text{HP}}$, אזי M תדחה את הקלט, ו‏־$CONT$ תעצור ותקבל את w, בסתירה לכך ש־$(\langle CONT\rangle ,w)\notin L_{\text{HP}}$.

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

תרגיל : הוכח, בעזרת משפט הרדוקציה, שהשפה $L=\{\langle M\rangle |M{\text{ on }}\varepsilon {\text{ outputs }}\langle M\rangle \}$ אינה כריעה
נניח, בשלילה שהשפה הנ״ל כריעה, ותהי R מ״ט שמכריעה אותה. נבנה מכונה חדשה $M'$ באופן הבא. $M'$ על קלט w: בעזרת משפט הרדוקציה, $M'$ רושמת את $\langle M'\rangle$ על סרט הזיכרון (מוחקת את w). $M'$ מריצה את R על הקלט $\langle M'\rangle$. אם R מקבלת, $M'$ מוחקת את סרט הזיכרון ומסיימת (הפלט הוא $\varepsilon$). אם R דוחה, $M'$ כותבת את $\langle M'\rangle$ על הסרט (בתור הפלט) ומסיימת.

משפט האי־שלמות של גדל

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

מערכת הוכחה

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

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

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

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

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

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

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

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

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

המערכת שאנו משתמשים בה ביום יום (באופן מובלע) נקראת ZFC, והיא חזקה דיו לתאר מ״ט. למשל טענה לגבי עצירה של מכונה M תהיה בסגנון הבא: קיימת סדרה $C_{1},C_{2},\ldots ,C_{n}$ כך שמתקיים (1) $C_{1}$ היא קונפיגורציה תחילתית של M (על קלט ריק); (2) לכל $i>1$ הקונפיגורציה $C_{i}$ היא הקונפיגורציה העוקבת של $C_{i-1}$; (3) $C_{n}$ היא קונפיגורציה סופית

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

1. בעזרת משפט הרקורסיה, M משיגה את הקידוד שלה $\langle M\rangle$
2. בעזרת $\langle M\rangle$ המכונה מגדירה את הטענה (המחרוזת) S

   S: "המכונה $M$ לא עוצרת על הקלט הריק"

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

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

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

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

לקריאה נוספת

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

הפרק הקודם: אי-הפרדתיות רקורסיבית

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

הפרק הבא: סיבוכיות קולמוגורוב