בתשובה לשייח ספיר, 02/11/07 9:51
ההוכחה? 461912
בסדר, הבה נתחיל מהטיעון של פנרוז אותו הצגת בתגובה ההיא - התיאור שלך לא מובן לי. אני מצטט פסקה מתוכו:

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

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

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

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

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

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

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

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

1. האם אתה טוען טענה אמפירית על יכולותיהם של אנשים, טענה החורגת ממגבלותיהם המוכחות של אלגוריתמים? אם כן, מהי?

2. האם אתה טוען, לחליפין, שאפשר להוכיח משהו על עולמם הפנימי של מחשבים? איך? עד כה, בסוף כל הטיעונים שלך ישבה התיזה "אנשים מבינים, מחשבים מבצעים פעולות מכניות חסרות משמעות". זו תיזה מצויינת, אבל היא אינה *נובעת* משום משפט של פנרוז שהצגת עד כה.

אתה יכול להציג כאן את הטיעון, או שאנחנו מתבקשים להמשיך ולהאמין שפנרוז הצליח לעשות משהו הנשגב מבינתנו (וחלקנו סבורים שהוא בלתי-אפשרי - למרות שקראנו בשקידה בספריו ומאמריו של האיש)?
ההוכחה? 462155
אני מוכן להסתפק (בינתיים) בתגובה על תגובה 461851.
ההוכחה? 462176
ההוכחה של פנרוז, שוב:
משפט: יהי (A(B,C אלגוריתם בשני קלטים*. A יכונה נאות אם מתקיים (A(B,C עוצר => (B(C איננו עוצר. נסמן ב-D את אלגוריתם האלכסון של A (בקלט אחד): (D(B)= A(B,B. אזי, אם A נאות, בהכרח:
1) (D(D אינו עוצר.
2) (A(D,D אינו עוצר.

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

מ.ש.ל

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

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

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

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

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

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

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

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

* קח אלגוריתם שאינו עוצר לעולם. הוא "נאות" במובן שלך. האם הוא "שיקולים לוגיים ומתמטיים נכונים"? לא, הוא לא מבצע שיקולים לוגיים ומתמטיים בכלל.

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

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

לכן שאלתי אותך לפני כמה תגובות על האינסוף. כל עוד עוסקים במבנים סופיים, גם אנשים וגם מכונות יכולים בקלות לוודא עקביות, שלמות ונאותות (במובן הרגיל של לוגיקה מתמטית!). ברגע שעוסקים במבנים אינסופיים, מה אז? איש אינו יודע אם ZFC עקבית - ואם היא לא, היא ודאי לא נאותה (למשל, אפשר אז להוכיח באמצעותה ש-‏0 שווה ל-‏1). איש אינו *יודע* שאקסיומת האינדוקציה "תקפה". יש לנו אינטואיציה (סופית!) מסויימת שהיא כן, ועל-כן עובדים איתה בשמחה ומקווים לטוב. אבל אין שום סיבה להניח שאלגוריתם לא יכול לרכוש את האינטואיציה הזו באותה מידה של הצלחה, ולשקול את אותם שיקולים כבני-אדם, ולקוות לטוב.

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

הארכתי יתר על-המידה. אם לומר כל זאת בקצרה, אתה מתחיל מטענה מאוד מלאכותית על אלגוריתם שהכרחת אותו להיות "בלתי-עוצר במצבים מסויימים" ואז מגלה בשמחה שהוא לא עוצר על עצמו, ומנסה להשליך מכך על חוסר היכולת של תהליכים חישוביים "לחקות מודעות". זו, פשוט, קפיצה חסרת כל-הצדקה.
ההוכחה? 462188
לא הארכת יתר על המידה. תודה.
ההוכחה? 462209
ראשית הערה כללית. פנרוז מקדיש כמחצית מספרו "Shadows of the mind" לדיון מפורט בטיעון שהצגתי. אינני יכול, מטבע הדברים, לחזור פה על כל הכתוב בספר. משום כך אני מדלג על לא מעט פרטים שנראים לי טכניים או צדדיים ומשתמש בניסוחים אינטואיטיביים ולא מדוייקים די הצורך. מי שרוצה להתעמק בפרטי הפרטים הטכניים של הטיעון מוזמן לעיין בספר. אני מסתפק ב-highlights.

את האלגוריתם X ההיפותטי המזהה נאותות של אלגוריתם אחר ניתן לשלב כחלק מאלגוריתם A, כך ש-(A(B,B יוכל לבחון באמצעותו האם A (הוא עצמו) הוא אלגוריתם נאות, ואם כן, להשוות את B לאלגוריתם האלכסון D של A, ואם B=D לעצור. זאת תהווה סתירה לנאותות של A, ומכאן נסיק שלא קיים X המזהה נאותות של אלגוריתם ש-X מהווה חלק ממנו.

ומה הקשר בין ה"נאותות" כפי שהגדרתי לנאותות של חשיבה מתמטית? חשוב על התחום המתמטי של חקירת עצירה של אלגוריתם. בעיה בתחום זה מספקת אלגוריתם B וקלט C ושואלת האם (B(C יעצור. אלגוריתם A' שיודע להסיק מסקנות נכונות בתחום זה יכול להחזיר 3 תשובות אפשריות: "עוצר", "לא עוצר" ו-"לא יודע". כעת, בנה מאלגוריתם זה אלגוריתם A בו הפלט "עוצר" והפלט "לא יודע" יופנו ללולאה אינסופית. A הוא נאות במובן של משפט פנרוז אם ורק אם A' נאות במובן המקובל בלוגיקה.

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

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

אגב, עניין הקונסיטנטיות של המערכות האקסיומטיות איננו רלוונטי. בהנתן מערכת F, את הטענה P תחת אותה מערכת אקסיומטית אפשר לבטא כטענה Q: F=>P. אם הוכחת את P תחת F, האמיתות של Q איננה תלויה בקונסיטנטיות של F. אם F איננה עקבית, הטענה הזו תהיה נכונה באופן ריק.

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

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

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

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

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

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

=======

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

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

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

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

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

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

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

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

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

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

"יש אלגוריתמים פשוטים מאוד המוכיחים משפטים נכונים בתורת המספרים, ואם כך הם 'ממדלים חשיבה מתמטית'; איך אתה מציע לייצר מהם אלגוריתם המזהה כל אלגוריתם עוצר על קלט נתון?" - לדוגמה, קח אלגוריתם המוכיח את משפט פרמה. מכאן הוא יסיק (לפחות אם הוא ניחן בתבונה אנושית) שאלגוריתם העובר על כל רביעיות המספרים הטבעיים a,b,c,n עם n גדול מ-‏2, ועוצר רק כאשר מתקיים a^n+b^n=c^n, בהכרח איננו עוצר.

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

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

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

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

חזרה לעמוד הראשי

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים