הפוסט שיודע להדפיס את עצמו

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

אם תנסו לכתוב תוכנית שכזו תגלו שזו משימה מעט טריקית. אתמקד בכתיבה בשפת התכנות רובי, שבה הכל יוצא “נקי” יחסית; פונקצית ההדפסה הסטנדרטית בשפה זו היא print. אם כן, נניח שאני רוצה לכתוב תוכנית שמדפיסה את עצמה ואני נוקט בגישה נאיבית, אז התוכנית שלי תהיה מהצורה “…” print, כאשר שלוש הנקודות בתוך המרכאות מייצגות את מה שאני רוצה להדפיס - במקרה זה, קוד התוכנית עצמה. הקוד של התוכנית מתחיל ב-print ולכן התוכנית תהיה חייבת להיות מהצורה ““…” print “print, אלא שכעת שיניתי את קוד התוכנית, ולכן מה שמקבלת פקודת ה-print חייב לגדול שוב, ושוב, ושוב - ולעולם לא אצא מזה. כלומר, הגישה הנאיבית נכשלת כשלון חרוץ. למי שעדיין לא הבין מה לעזאזל השתבש - פשוט נסו לכתוב את התוכנית בעצמם, זה ייתן מייד את התחושה (אין צורך לדעת לתכנת - מספיק להכיר את פקודת print ותו לא).

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

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

הרעיון הוא לבנות מכונה שמורכבת משתי “תת מכונות”, \( A,B \), כך ש-\( A \) עושה משהו ואז עוצרת, והשליטה עוברת ל-\( B \) שגם כן עושה משהו ועוצרת, ואחרי שהיא עוצרת על הסרט יהיה כתוב הקידוד של \( A \) ולאחר מכן הקידוד של \( B \), מה שאסמן בתור \( \left\langle AB\right\rangle \). על פניו אני קצת מרמה כאן טכנית - בהגדרות מקובלות של קידודי מכונות טיורינג לא מרשים “פירוק” כזה של מכונה לשתי תת מכונות. אלא שאין בעיה עם הגדרה שכן מרשה “פירוק” שכזה; וכפי שנראה בהמשך, ההנחה אפילו לא הכרחית, רק מפשטת את ההבנה של הבניה.

אם כן, מה \( A \) תעשה? פשוט מאוד - תכתוב את הקידוד של \( B \) (כלומר, \( \left\langle B\right\rangle \)) על הסרט ואז תעצור. אבל רגע, מאיפה \( A \) יודעת מה הקידוד של \( B \)? עדיין לא אמרנו מהי \( B \) בכלל! אם כן, עלינו להגדיר את \( B \) במדוייק, אבל להיות מאוד זהירים כשנעשה זאת; אם \( B \) תהיה תלויה באופן כלשהו ב-\( A \), תהיה לנו כאן תלות מעגלית (הקוד של \( B \) תלוי ב-\( A \), אבל מכיוון ש-\( A \) מדפיסה את הקוד של \( B \), בוודאי שהקוד של \( A \) תלוי ב-\( B \)!). לכן נגדיר את \( B \) בלי לדבר בכלל על \( A \).

כש-\( B \) “מתעוררת” כתוב קלט כלשהו על הסרט. נקרא לו \( w \). מה שב-\( B \) תעשה יהיה לבנות קידוד של מכונה שכל ייעודה בחיים הוא לכתוב את \( w \) על הסרט ולעצור. זה רעיון מעט מחוכם, אבל לא קשה במיוחד. נסו לחשוב האם אתם יכולים, בהינתן קלט \( w \) כלשהו, לכתוב תוכנית מחשב שכל מה שהיא עושה הוא לכתוב \( w \) ולעצור; ואם כן, האם אתם מסוגלים לכתוב פונקציה שמקבלת \( w \) כקלט ומוציאה כפלט קוד של תוכנית מחשב שמדפיסה את \( w \)?

אם כן, נסמן ב-\( M_{w} \) מכונת טיורינג שמה שהיא עושה הוא לכתוב \( w \) על הסרט ולעצור. אז מה ש-\( B \) עושה הוא לבנות את \( \left\langle M_{w}\right\rangle \) ולכתוב אותו ליד הקלט \( w \) הקיים, כלומר בסופה של ריצת \( B \) יהיה כתוב על הסרט \( \left\langle M_{w}\right\rangle w \). כדי להיות עוד יותר מדוייקים נדבר ממש על פונקציה, \( q \), שמקבלת כקלט \( w \) ומוציאה כפלט קידוד של \( M_{w} \) ספציפית (שהרי יש הרבה מכונות שונות שכותבות \( w \) על הסרט ועוצרות).

תיארנו את \( B \) בלי להזדקק ל-\( A \), ולכן אין בעיה לכתוב מכונה \( A \) שכל מה שהיא עושה בחיים הוא לכתוב \( \left\langle B\right\rangle \) על הסרט ולעצור. כאן מגיע הפאנץ’: אפשר בתור \( A \) לבחור את המכונה שהקידוד שלה הוא \( q\left(\left\langle B\right\rangle \right)=\left\langle M_{\left\langle B\right\rangle }\right\rangle \)! כלומר, את המכונה שאת הקידוד שלה הפונקציה \( q \) מחזירה. האם אתם כבר רואים לאן הולכים מכאן?

אז מה ש-\( A \) עושה הוא לכתוב \( \left\langle B\right\rangle \) על הסרט ולעצור. אז \( B \) “מתעוררת”, רואה קלט \( w=\left\langle B\right\rangle \) (\( w \) הוא הקידוד של \( B \), אך \( B \) לא “יודעת” זאת), ומחשבת את \( q\left(\left\langle B\right\rangle \right)=M_{\left\langle B\right\rangle }=\left\langle A\right\rangle \). לסיום היא כותבת את הפלט הזה משמאל ל-\( w \) שהיא קיבלה, כלומר בסיום ריצת \( B \) כתוב על הסרט \( \left\langle AB\right\rangle \), בדיוק כפי שרצינו. תעלול פשוט, אך מבריק.

כעת אפשר להסביר מדוע ההנחה שהקידוד של המכונה מורכב קודם כל מהקידוד של \( A \) ולאחר מכן מהקידוד של \( B \) היא לגיטימית - כי מה שקורה ל-\( B \) בסופו של דבר היא שהיא מחזיקה אצלה הן את הקידוד של \( A \) (בתור ה-\( q\left(w\right) \) והן את הקידוד של \( B \) (בתור ה-\( w \)) והיא יכולה לעשות איתם מה שמתחשק לה. אנחנו ביקשנו ממנה לרשום אותם האחד אחרי השני, אבל אם היה צורך להשתמש בהם באופן מחוכם יותר, \( B \) הייתה יכולה לעשות גם את זה. בעצם כל מה שאנחנו מניחים הוא שאם יש לנו מכונה שמורכבת משתי תת-מכונות \( A,B \) ויש לנו את הקוד של אותן שתי תתי-מכונות, אז אפשר לבנות את הקוד של המכונה ה”מורכבת” - וזה דבר שאני מניח שתסכימו איתי שהוא אפשרי.

עכשיו אפשר לקחת את הבניה הזו צעד אחד קדימה ולבנות מכונה שיודעת להשתמש בקוד של עצמה כמה שתרצה. לצורך העניין, נחשוב על מכונה \( T \) שמקבלת שני פרמטרים, \( \left\langle M\right\rangle ,w \), כאשר \( w \) הוא הקלט ה”רגיל” של המכונה ואילו \( \left\langle M\right\rangle \) הוא קידוד של מכונה כלשהי, ו-\( T \) פועלת כפונקציה של שני הקלטים הללו. מה שאנחנו רוצים להראות הוא קיום של מכונה \( R \) כך ש-\( R\left(w\right)=T\left(\left\langle R\right\rangle ,w\right) \). כלומר, \( R \) מתנהגת כמו \( T \) בכל הנוגע לקלט \( w \), ועבור הקוד \( \left\langle M\right\rangle \) שלה עצמה. מבלבל? אז חשבו על תוכנית מחשב שמקבלת קלט מהמשתמש ועוד משתנה של “הקוד שלי”; אנחנו רוצים לגרום לתוכנית לרוץ כך שהמשתנה “הקוד שלי” יכיל את הערך הנכון.

אין כאן שום גאונות חדשה, אלא רק הרחבה פשוטה של הבניה שכבר ראינו. נוסיף את הקוד של המכונה \( T \) למשחק, כך שהיא תתחיל לפעול אחרי \( B \), ולכן הקוד של המכונה ה”משולשת” יהיה \( \left\langle ABT\right\rangle \). מה ש-\( A \) יעשה הפעם יהיה לכתוב \( \left\langle BT\right\rangle \) על הסרט, ואילו \( B \) יעשה בדיוק את אותו הדבר כמו קודם ויחשב את \( \left\langle A\right\rangle \). כש-\( B \) יסיים את ריצתו על הסרט יהיה כתוב \( \left\langle ABT\right\rangle \) וזה בדיוק מה ש-\( T \) תראה כאשר היא תתחיל את ריצתה (ואיפה הקלט של \( T \) נמצא? אפשר להניח שכבר \( A \) שמרה אותו בצד - זה לא גורר שינוי משמעותי בהגדרות שלנו).

ועכשיו - לקוד בפועל, בשפת רובי, שמשתמש בדיוק ברעיונות שתיארתי כאן:

b = "\n\ndef q(w)\n\t\"b = \#{w.inspect}\"\nend\n\nprint q(b) + b"

def q(w)
    "b = #{w.inspect}"
end

print q(b) + b

לא צריך לדעת יותר מדי רובי כדי להבין מה קורה כאן. הדבר המחוכם ביותר הוא האופן שבו אני מתאר מחרוזת: בתוך מחרוזת אני יכול לכתוב ביטויים כמו n\ ו-t\ שמתפרשים בתור התווים המתאימים לירידת שורה או לטאבים. מה שכתוב בתוך השורה הראשונה בקובץ הוא פשוט כל יתר השורות בקובץ. כל זה מושם בתוך המשתנה b; חשבו על זה בתור הריצה של \( A \), שכותבת את המחרוזת שמתארת את \( B \) לא על ה"סרט" (כי אין סרט) אלא לתוך המשתנה b.

החל מהשורה השניה מגיע התיאור של \( B \). ראשית, הפונקציה \( q \) שמקבלת \( w \) ופולטת תוכנית שמה שהיא עושה בחיים הוא להדפיס את \( w \). האופן שבו היא עושה את זה הוא המקום העיקרי שבו צריך להבין טיפה רובי. ראשית, ברובי לא חייבים לכתוב במפורש return כדי להחזיר ערך מפונקציה; הערך האחרון שמחושב בתוך פונקציה הוא אוטומטית ערך ההחזרה שלה. לכן הפונקציה בת השורה הבודדת הזו כוללת רק מחרוזת, והמחרוזת הזו אוטומטית תהיה הפלט של הפונקציה.

שנית, כשאני כותב מחרוזת בשפת רובי אני יכול “להשתיל” בתוך המחרוזת ערכים של ביטויים. התחביר עבור “השתלה” כזו הוא כתיבה של סולמית (#) ואז את הביטוי שאני רוצה להשתיל במחרוזת כשהוא בתוך סוגריים מסולסלים. במקרה שלנו אני משתיל את הערך של w, אבל לא לפני שאני מבצע שינוי כלשהו לערך הזה באמצעות הפעלת הפונקציה inspect עליו. הפונקציה הזו, כשהיא מופעלת על מחרוזת, מחזירה גרסה חדשה של המחרוזת שכתובה בצורה יותר מפורשת. למשל, אם במחרוזת המקורית היה תו של ירידת שורה (ולכן כשהמחרוזת הייתה מודפסת על המסך הייתה מופיעה ירידת שורה) הרי ש-inspect החליפה את התו הזה בזוג תווים, n\; זה מתאים לאופן שבו תיארתי את ירידת השורה בתוך המחרוזת b מלכתחילה. במהלך ריצת התוכנית מה שקורה הוא שראשית המשתנה b מאותחל על ידי לקיחת המחרוזת ששמים לתוכו וביצוע כל מני המרות בה שהופכות זוג רצוף של תווים כמו n\ לתו ירידת שורה; inspect פשוט מבצעת את התהליך הזה בכיוון ההפוך.

לאחר הגדרת \( q \) מגיע יתר הקוד של \( B \); ראשית היא מחשבת את \( q \) על “תוכן הסרט” הנוכחי (כלומר, על המשתנה b) ומקבלת תוצאה שהיא \( \left\langle A\right\rangle \); וכעת היא פולטת את השרשור של הפלט הזה עם התוכן של b, בדיוק כמו ש-\( B \) התיאורטית שלי עבדה.

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