בתשובה לאלון עמית, 27/04/05 1:44
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296249
תובל • בתשובה לאלון עמית יום ד', 27/4/2005, 2:06
"בגלל המשפט המפתיע הזה נוצר הצורך להבין את גבולות היכולת של מערכות פורמליות שונות, למה ניתן לצפות ולמה לא ניתן לצפות"

אתה יכול להרחיב קצת לגבי הנקודה הזאת? (כלומר, מה משפט גדל שינה לגבי התפיסה שלנו את גבולות היכולת של מערכות פורמליות שונות?)
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296251
אלון עמית • בתשובה לתובל יום ד', 27/4/2005, 2:32
פשוט מאוד: הוא הראה שיש כאלה (גבולות, זאת אומרת). לפני גדל, קיוו לבנות מערכת פורמלית שבתוכה ניתן יהיה להוכיח או להפריך כל טענה בתורת-המספרים, נניח. בעקבות המשפט, הבינו שלא ניתן לצפות שמערכת פורמלית אחת תיתן מענה לכל השאלות. למערכת פורמלית נתונה יש "כוח" מסויים (דברים שהיא מסוגלת להראות), והכוח הזה לא תמיד מתלכד עם מה שהיית רוצה (דברים שהיא מסוגלת לדבר עליהם). לדוגמה, אף מערכת פורמלית (מעניינת, עקבית) איננה מסוגלת להוכיח את העקביות של עצמה, למרות שהרבה מערכות פורמליות מסוגלות לנסח את העקביות של עצמן כטענה (כלומר "לדבר על זה").

השינוי התפיסתי הרחב יותר הוא שמאז גדל, בכל פעם שמנסים להתמודד עם שאלה שנראית מסובכת, במיוחד שאלות בעלות אופי מאוד כללי (אלגוריתם הבודק אם יריעה היא כדור, השאלה אם P=NP, תהליך לבדיקת פתירות של משוואה דיופנטית), מנקר תמיד החשש שמא התשובה היא שאין תשובה (במסגרת האקסיומטית הנוכחית). לפעמים החשש אפילו מיתרגם לעובדה, לפעמים לא, אבל הוא בכל מקרה שם, ואני חושב שהוא לא ממש היה שם לפני 1931.
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296259
תובל • בתשובה לאלון עמית יום ד', 27/4/2005, 3:35
בגלל הבורות שלי בתחום אני לא כ"כ מבין מה זה אומר " מערכת שאיננה מסוגלת להוכיח את העקביות של עצמה"

אגב, יש אפשרות להסביר את ההוכחה המתמטית של גדל בצורה שתהיה מובנת לאנשים חסרי השכלה מתמטית?
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296261
אלון עמית • בתשובה לתובל יום ד', 27/4/2005, 4:33
בטח שיש. בשביל מה המציאו את הופשטטר? (תגובה 4582, תראו כמה מזמן הספר הזה הופיע באייל...). לא שצריך כל-כך הרבה עמודים בשביל זה, אבל זה ספר שלדעתי כדאי לקרוא (למרות מגרעותיו). יש עוד ספרים פופולריים על ההוכחה, אבל לא עולה לי בראש שם מתאים. אם תרצה אחפש.

לשאלתך הראשונה: מערכת פורמלית של תורת המספרים מאפשרת לנסח טענות על מספרים. זה פשוט אוסף של סימנים מוסכמים (כמו "0", "y", "+", "=") וכל-מיני כללים האומרים איך אפשר לחבר את הסימנים האלה לפסוקים, מה האקסיומות, ומה הכללים המאפשרים להסיק מסקנות. פסוק יכול להיות משהו כמו

A x E a,b,c,d | x=a^2+b^2+c^2+d^2

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

אם אפשר לנסח את הטענה הזו, הצעד הבא הוא לנסות להוכיח אותה. את זה אי-אפשר לעשות, לא ב-PA. אפשר לעשות זאת בתוך מערכת חזקה יותר, אבל אז את העקביות *שלה*... וכו'.
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296262
רון בן-יעקב • בתשובה לאלון עמית יום ד', 27/4/2005, 5:16
אולי אני טועה, אבל יכול להיות שההסבר הברור שלך הזכיר לי במעומעם קורס בחישוביות(?) שלקחתי לפני שנות אלף אצל שוויקה?
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296267
אלון עמית • בתשובה לרון בן-יעקב יום ד', 27/4/2005, 8:26
היחיד שיכול לומר אם זה הזכיר לך או לא זה בעל הזיכרון - אתה (יש על זה מאמר מעניין באייל שהתפרסם לאחרונה, לא זוכר של מי. כדאי לך לקרוא).

כן, בטח שיכול להיות... התוצאות הבסיסיות בחישוביות דומות מאוד.
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296394
תובל • בתשובה לאלון עמית יום ד', 27/4/2005, 13:20
תודה
אומרים שמייקל ג'ורדון שיחק בייסבול די גרוע 296253
אלון עמית • בתשובה לתובל יום ד', 27/4/2005, 2:38
(אני לא בטוח שעניתי על השאלה, אם צריך אולי תוכל לחדד אותה קצת).
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות