בתשובה לאלון עמית, 06/11/07 11:58
ההוכחה? 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 (זו למעשה תוצאה ממשפט פנרוז). משום כך אי אפשר לומר שיש לה "ידע" בדבר הנאותות של עצמה. ידע איננו הצהרה סתמית. הוא משהו שניתן להשתמש בו לשם הסקת מסקנות.

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

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