המותר האדם מן האלגוריתם, חלק 2 - הנקמה?

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

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

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

פנרוז תיאר את העסק בצורה יותר מסובכת עם ביטויים כמו \( M_{k}\left(k\right)=1+M_{k}\left(k\right)\times H\left(k,k\right) \), אבל זה מיותר לגמרי, כפי שאמרתי בפוסט הקודם; לצורך פשטות מספיק לתאר את \( Q \) באופן הבא: \( Q \) מריצה את \( H \) על הקוד של \( Q \) (\( Q \) יכולה לדעת מה הקוד של \( Q \); זהו משפט הרקורסיה של קלייני) ואם \( H \) אמרה ש-\( Q \) עוצרת, אז \( Q \) לא עוצרת; ואם \( H \) אמרה ש-\( Q \) לא עוצרת, אז \( Q \) עוצרת. זהו. שימו לב שכאן אין התייחסות בכלל לקלט של \( Q \); אפשר לחשוב עליה כעל מכונה שלא מקבלת קלט, או שההתנהגות שלה לכל הקלטים היא אותו דבר ו-\( H \) נשאלת על ההתנהגות של \( Q \) על קלט ספציפי, וכדומה. אני חושב שדרך ההצגה שלי מזקקת את לב הבעיה.

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

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

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

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

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

בואו ננסה לעשות את הבניה הטבעית ביותר: \( P \) על מכונה \( M \) בודקת קודם כל אם \( M \) יכולה להתקבל כ-\( Q \) של איזו מכונה \( H \), ואם היא יכולה, אז \( P \) אומרת ש-\( M \) לא עוצרת… רגע, רגע, הויסה. יש לנו שתי טעויות גסות בשורה האחרונה.

ראשית, יש אינסוף מכונות \( H \), אז רק שלב הבדיקה אם \( M \) היא \( Q \) של \( H \) כלשהי יכול להימשך לנצח. אם \( M \) אינה מתאימה לאף \( H \), אז החיפוש הזה לא יסתיים אף פעם. אפשר לנסות ולעקוף את הבעיה הזו כך - במקביל לביצוע החיפוש, \( P \) גם יבצע הרצה של \( M \). אם \( M \) עוצרת, אז \( P \) תענה ש-\( M \) כן עוצרת. אפשר גם לזרוק פנימה בדיקות קצת יותר מחוכמות האם \( M \) עוצרת או לא. הנקודה היא שהבדיקה אם \( M \) היא “מכונה שמכשילה \( H \) כלשהו” יכולה להתבצע במקביל ובאופן בלתי תלוי לשאר הבדיקות; זה סתם עוד כלי נשק של \( P \). אם כן, לכל מכונה \( H \) שפותרת את בעיית העצירה באופן חלקי, \( P \) בריצתו על \( Q \) יגיד בודאות ש-\( Q \) לא עוצרת (כי הוא יגלה ש-\( Q \) היא המכונה שמכשילה את \( H \) הספציפי הזה; הוא יגיע אל \( H \) במהלך הבדיקה שלה).

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

בואו ניקח כדוגמה \( H \) שעוצרת תמיד עם הפלט 0. אז ה-\( Q \) המתאימה לה (שכזכור, מריצה את \( H \) ועושה הפוך ממה שהיא אומרת) תעצור מייד. זה מראה ש-\( H \) לא פותרת את בעיית העצירה כי היא טועה על הקלט \( Q \); אבל גם \( P \) לא פותר את בעיית העצירה כי גם הוא יגיד ש-\( Q \) אינה עוצרת, ולכן יטעה. כדי ש-\( P \) יעבוד בהצלחה, הוא חייב לבדוק האם \( M \) היא \( Q \) של איזו מכונה \( H \) רק עבור מכונות \( H \) שפותרות חלקית את בעיית העצירה. אבל, וזו הנקודה המרכזית, למיטב ידיעתנו אין ל-\( P \) יכולת לעשות זאת! לא קשה להוכיח שהבעיה של “זיהוי האם \( H \) פותרת חלקית את בעיית העצירה” היא קשה עוד יותר מפתרון בעיית העצירה (פורמלית, זו בעיה שאפילו אינה ב-RE). לכן, רק להראות ש-\( P \) מסוגלת לבצע את אותו שלב בדיקה כבר דורש מאיתנו להראות ש-\( P \) חזקה יותר מכל מכונת טיורינג. שוב - “אם האדם חזק מהמכונה, אז האדם חזק מהמכונה”.

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

למעשה, לא ברור איפה פנרוז משתמשת ביכולותיו של האדם בכל הסיפור הזה - כפי שכבר ראינו, את \( Q \) אפשר לבנות מ-\( H \) באופן אלגוריתמי. כך שאפשר לנסח את מה שפנרוז מראה גם בתור “לכל \( H \) שמנסה לפתור את בעיית העצירה קיימת \( H^{\prime} \) שפותרת את בעיית העצירה יותר טוב ממנה”. אז איפה מותר האדם מן המכונה פה?

פנרוז מציין במפורש שאותה \( H^{\prime} \) משופרת קיימת, אבל הוא מעיר בהערת שוליים שגם אותה אפשר להביס עם טיעון דומה (והוא צודק), ושגם את \( H^{\prime} \) אפשר יהיה לשפר עם איזו \( H^{\prime\prime} \) (והוא צודק), ושהוא ידון ב”סוג השיקולים שהתהליך האיטרטיבי הזה מוביל אותנו אליו” בפרק שעוסק במשפטי גדל. הוא אכן עושה זאת שם, אבל רק בהקשר של תורות פורמליות ולא של מכונות טיורינג, והוא לא נכנס לעובי הקורה; הוא מתאר קצת איך אפשר להמשיך עוד ועוד את הבניה (ומערב בתמונה אורדינלים) ממלמל משהו על כך שתהליך הבניה האיטרטיבי מוביל אותנו ל”שיקולים מתמטיים קשים שלא ניתן להיכנס לפרטיהם כאן” ומפנה למאמר (מרתק ובלתי קריא) של טיורינג בנושאים הללו. אנסה כנראה להקדיש פוסט לאותו מאמר מתישהו; אבל עבור פנרוז העיסוק בנושא נגמר כאן פחות או יותר (אלא אם הוא חוזר אליו בפרקים מאוחרים יותר) מבלי שהוא הסיק מתמטית שום מסקנה חד משמעית. בהמשך הוא מציג עוד מושגים יפים מחישוביות וכמה בעיות לא כריעות מפורסמות (הבעיה העשירית של הילברט, בעיית המילה, בעיית הריצוף) אבל לחזור מתמטית לכל עניין ה”האדם יודע לפתור את בעיית העצירה יותר טוב מכל מכונה”? לא.

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

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

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

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

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