בתשובה לאלון עמית, 27/04/10 10:43
 |
|
 |
||
|
||||
 |
>> עוזי, אורי: אני עדיין מחכה לנימוקים טובים נגד ההנחה שלכל פסוק המנוסח בשפה מסדר ראשון על הטבעיים יש ערך אמת אני לא עוזי ולא אורי, אבל באייל מקובל להידחף: ראיתי את השאלה הזו מועלית על ידך בהרבה מקומות באייל, והתשובה תמיד נראתה לי טבעית וטריביאלית אבל חיכיתי שמתמטיקאי אמתי יגיב. כיוון שעכשיו דקה לסגירה אני מפסיק לחכות: הבעייתיות עם האמירה\הנחה הזו, להבנתי היא במילה הקטנה "יש". זה לא מושג מתמטי מוגדר היטב, ואם תנסה לדייק ולהבהיר למה אתה מתכוון *בדיוק* כשאתה אומר "יש" אז התשובה, "כן" או "לא" תצוץ, כתלות בהגדרת ה"יש". כל עוד אין הגדרה, גם התשובה לשאלה נמצאת עדיין במעין ענן הסתברות, מחכה להגדרה ש"תמוטט" את הענן למצב ידוע1 אני יודע שאתה מאמין שהתשובה היא "כן", וזה אולי רומז למה אתה מתכוון כשאתה אומר "יש", אבל עד שלא תגדיר זאת הגדרה מתמטית טובה, לא תוכל לקבל תשובה מתמטית לשאלה. 1 אמנם מטאפורה מפיסיקה ולא מתמטיקה, אבל נראתה לי מתוקה מדי לוותר עליה. |
 |
 |
 |
|
|
|
||
|
||||
|
קיימת פונקציה המתאימה לקבועי השפה מספרים טבעיים, ליחסי השפה תת קבוצות של מכפלות קרטזיות של מספרים טבעיים וכו' וכו' כך ש<בלה בלה בלה סמנטיקה שבסופו הפסוק מקבל T> או שלא קיימת פונקציה כזו. לא? |
|
|
|
|
|
|
||
|
||||
|
אם אני מבין נכון (לצערי השכלתי המתמטית נקטעה מוקדם יותר משרציתי מאילוצים כלכליים), ואם אלון אכן מתכוון ב"יש" למשמעות שאתה מתאר, אז שאלתו ניתנת לתרגום ל"משפט אי השלמות לא תופס". כיוון שפירוש זה הוא בלתי אפשרי מבחינה פיזיקלית (כלומר לא יתכן שזה מה שאלון באמת אומר) הרי שאו שאתה שוגה ואלון מתכוון למשהו אחר כשהוא אומר "יש", או שאני שוגה בהבנתי את המשתמע ממה ש*אתה* אומר. עזור לי: האם צדקתי בהבנתי שמה שאתה אומר אכן מתפרש כ"משפט אי השלמות אינו נכון"? או אולי זה בעצם "קיימת מערכת אקסיומטית ואפקטיבית יותר "חזקה" מ ZFC שבמסגרתה <כל הבלה-בלה-בלה שאמרת> עבור הטבעיים"? או משהו אחר שלא קשור בכלל לשאלת השלמות? תודה. |
|
|
|
|
|
|
||
|
||||
|
בוודאי שמשפט אי השלמות תופס. אני לא רואה את הרלוונטיות של זה למה שאלון אמר (אלון דיבר על כך שמשפט הוא נכון או לא נכון במודל של המספרים הטבעיים; משפט אי השלמות מדבר על כך שיש משפטים שאינם ברי הוכחה למרות שהם נכונים במודל זה. הוכחה היא מושג נפרד מ"נכונות" - למעשה, זה בדיוק מה שמשפט אי השלמות מראה). | |
|
|
|
|
|
||
|
||||
|
אז כנראה שלא הבנתי. חשבתי שההגדרה שלך למושג ''נכונות'' שקולה להוכחה (כלומר אם יש פונקציה כמו שתיארת, חשבתי שקיום הפונקציה שקול ל''הוכחה'', לא ל''נכונות'') |
|
|
|
|
|
|
||
|
||||
|
הוכחה תלויה מאוד באקסיומות וכללי ההיסק שלנו. גם אם הפונקציה המדוברת קיימת, זה לא אומר שנוכל להוכיח את קיומה בעזרת מערכת ההוכחה שלנו. | |
|
|
|
|
|
||
|
||||
|
שוב לא הבנתי. האם כוונתך שהפונקציה הנ"ל קיימת אלא שכדי להוכיח את קיומה נחוצה "מערכת הוכחה" חזקה יותר, או שלפונקציה יש "קיום" אלא שקיום זה לא ניתן להוכחה? האם האפשרות הראשונה משמעותה שאפשר (אולי) "לשכן" את ZF בתוך מערכת אכסיומטית "חזקה" יותר באופן שכל טענה נכונה ב־ZF היא יכיחה במערכת החזקה יותר, או שכוונתך שלכל טענה נתונה קיימת מערכת כזו אלא שזו מערכת שונה עבור כל טענה? האם המשפטים שכתבתי למעלה נשמעים כמו משהו שהיית מצפה לשמוע ממשה קליין? |
|
|
|
|
|
|
||
|
||||
|
נחוצה מערכת הוכחה חזקה יותר. תמיד אפשר לקחת מערכת הוכחה מטופשת שבו קיומה של הפונקציה הזו היא אקסיומה, כך שאי אפשר לומר שהקיום של הפונקציה לא ניתן להוכחה "בכלל". אגב, קל מאוד לשכן את ZF בתוך מערכת אקסיומטית חזקה יותר - תוסיף ל-ZF את אחד מהמשפטים שנובעים מ-ZF והופס - קיבלת מערכת שמוכיחה כל טענה שניתנת להוכחה מ-ZF (וכמובן, יש הרחבות מקובלות ל-ZF שאינן מטופשות אלא מוסיפות משהו שאינו יכיח מ-ZF, למשל אקסיומת הבחירה). לשאלתך האחרונה - לא. |
|
|
|
|
|
|
||
|
||||
|
השיכון ב"מערכת מטופשת" הוא חסר ערך, משום שאם ה"מערכת המטופשת" אינה עקבית אפשר "להוכיח" גם טענות שקריות, ולכן אין לראות בהוכחה בעזרת "מערכת מטופשת" ראיה ל"נכונות", אלא ניסוח מחדש של הטענה: במקום הטענה המקורית צצה טענה חדשה: ה"מערכת המטופשת" עקבית. זה לא הרבה יותר מטאוטולוגיה פשוטה. כיוון שאין לנו דרך לבדוק עקביות של "מערכת כלשהי"1, אני לא רואה איך ההגדרה שסיפקת בתגובה שפתחה את הפתילון הקטן בינינו מגדירה "נכונות" באופן שיעזור לענות על השאלה של אלון (או אפילו השאלה שלי). להבנתי, השאלה של אלון ממנה התחיל הדיונון הזה שקולה לשאלת הזן הידועה על עץ שנופל ביער אך אין מי שישמע. מה משמעות האמירה "יש לטענה ערך אמת"? באיזה אופן ערך האמת הזה "קיים"? אם מישהו דתי, אפשר לדחוף את זה קצת קדימה ולהגיד ש"יש"2 איזשהו אלהים שיודע אם הטענה נכונה או לא, ולכן יש לה "ערך אמת מוגדר היטב". אבל למי שאינו דתי עדיין לא ברור מה הוא סוג ה"קיום" הזה שאלון מאמין בו, כמו שלא ברור מה משמעות ה"רעש" שעושה (או לא עושה) האלון הנופל ביער כשאין מי שיוכל לשמוע. 1 לפחות כך הבנתי. 2 "לדחוף קדימה" משום שהשאלה הבאה היא מה משמעות ה"קיום" שמיוחס לאותו אלהים, ואז מתברר שבעצם "התקדמנו אחורה" כמו שאה״ל לא אהב שאומרים. |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח שהבנתי משהו משתי הפסקאות הראשונות שלך. על כל פנים, אנסה שוב לחדד את הנקודה העיקרית: בלוגיקה יש מושג פורמלי וסינטקטי של הוכחה - סדרת סדרות של סימבולים שהיא חוקית או לא חוקית על פי כללים צורניים מסויימים. זה לחלוטין לא מה שאני מדבר עליו או מה שלדעתי אלון מדבר עליו, וזה לחלוטין לא רלוונטי. מה שאנחנו מדברים עליו נוגע לסמנטיקה, לא לסינטקטיקה. ולדעתי כשעץ נופל ביער נוצרים גלי קול, אז כן - יש רעש. |
|
|
|
|
|
|
||
|
||||
|
אני חושב שאני מבין את ההבדל בין "נכונות" ל"הוכחה". השאלה של אלון התייחסה ל"נכונות": "האם לכל משפט יש ערך אמת". אני אמרתי שלהבנתי המושג "יש" לא מוגדר היטב, (בניגוד למושג ההוכחה). אתה הבאת הגדרה שנמצאת בערך מטר וארבעים מחוץ למגבלות ידיעותי המתמטיות ל"נכונות", ואחרי הרבה התבחבשות במהלכה כנראה גם הקלדתי לא מעט שטויות מתברר שאנחנו חזרה ב"הוכחה". כאן אני נאלץ להרים ידיים, לצערי בלי שהצלחתי להחכים הרבה :( לגבי העץ ביער: כנראה שבאמת יווצרו שינויים בלחץ האויר בתדירויות כאלו ואחרות. להבנתי (המוגבלת מאד בנושא - זן אני מבין הרבה פחות ממתמטיקה) שאלת הזן מנסה לגרום לך לשאול את עצמך מה הכוונה ב"רעש", ומה משמעות ה"קיום" שלו בלי שומע. זה דומה באופן מפתיע להבנתי את הבעיה בשאלתו של אלון: מה משמעות ה"קיום" של אותו ערך אמת: אם אף אחד לא יכול לדעת (לשמוע), אז באיזה אופן ערך האמת (הרעש) קיים, ומה המשמעות של קיום זה? |
|
|
|
|
|
|
||
|
||||
|
אני יודע מה שאלת הזן מנסה לעשות, ולדעתי היא התחכמות לא מועילה. ברור שהשינויים בלחץ האוויר קיימים. ברור שהם לא באים לידי ביטוי בפעילות נוירונית מסויימת במוח של יצור שיש לו אמצעי קליטה עבורם. לכן יש רעש במובן הפיזיקלי, ואין רעש במובן ה''תחושתי''. אף פעם לא הבנתי למה להסתבך כל כך עם השאלה הזו. בנוגע לקיום של ערך האמת - ניסיתי לתת את מה שלטעמי היא הגדרה מדוייקת ופשוטה, כמו שינויי לחץ האוויר. כמובן שכמו עם הרעש התחושתי, גם כאן אפשר לתת מאה ואחת הגדרות אחרות, ובפרט כאלו שמקדשות את העמימות ומקשות על מתן תשובה חד משמעית לשאלת הקיום. |
|
|
|
|
|
|
||
|
||||
|
לגבי שאלת הזן, אם תחליף את העץ באלקטרון, את 'נופל' ב-'עובר בחריץ אחד מתוך שניים אפשריים' ואת 'משמיע רעש' ב-'משמיע קליק בגלאי ליד אחד החריצים', אולי זה יעזור להבין למה שווה להסתבך עם השאלה הזו. (הפונז שמח על התירוץ החצי אפוי להוסיף הערה בדיון ההיסטורי - והעצוב קמעה - על סגירתו של האייל, סניפ סניפ) |
|
|
|
|
|
|
||
|
||||
|
מילא אלקטרונים. אבל קורים בספרים דברים כל־כך מוזרים עם מספרים טבעיים? | |
|
|
|
|
|
||
|
||||
|
ההפך - זה יראה למה שאלת הזן חסרת טעם, לעומת השאלה הפיזיקלית. | |
|
|
|
|
|
||
|
||||
|
ואני לתומי חשבתי שברמה העקרונית זאת בדיוק אותה שאלה. | |
|
|
|
|
|
||
|
||||
|
לחלוטין לא. שאלת הזן לא עוסקת, למיטב הבנתי, באופן שבו מדידה משפיעה על המציאות. | |
|
|
|
|
|
||
|
||||
|
היא עוסקת, למיטב הבנתי, באופו בו צופה משפיע על המציאות1. עכשיו עברנו לשאלה האם מדידה מצריכה צופה, ומכאן המדרון חלקלק לחתולים של גרמנים עם שמות ארוכים ושאר חיות משונות. לו היתה בקיאותי באייל רבה יותר, וודאי יכולתי לשים לינקים לדיונים שעסקו בכך בהרחבה (כולל מאמר אחד לפחות בכמה חלקים, אם זכרוני אינו מטעני). אי לכך לא בטוח שאנו רוצים לגלוש כאן במדרון הזה. 1 ואולי אף בשאלה מהי מציאות, כנראה... |
|
|
|
|
|
|
||
|
||||
|
ארווין! מה עשית לחתול הוא נראה חצי מת? | |
|
|
|
|
|
||
|
||||
|
גרטשן! אמרתי לך לא להציץ לתוך הקופסה! את לא מכירה את המשל על הסקרנות והחתול? | |
|
|
|
|
|
||
|
||||
|
היה לי פעם, אבל בא איזה גרמני אחד וביקש אותו לניסוי. מאז יש לי רק שמונה וחצי נשמות, או יותר נכון, אני בסופרפוזיציה של תשע נשמות ושמונה נשמות. מה לעשות שזה לא ניק קליט במיוחד, אז נשארתי עם ''תשע נשמות''. | |
|
|
|
|
|
||
|
||||
|
שרדינגר היה אוסטרי. | |
|
|
|
|
|
||
|
||||
|
אתה לא רק עוכר ישראל, אתה גם עוכר שמחות. | |
|
|
|
|
|
||
|
||||
|
לא יפה. עד שיש לי הזדמנות להסכים עם ארז ולהודות שהוא צדק ואני טעיתי? | |
|
|
|
|
|
||
|
||||
|
היה כאן מגיב שהשתמש תקופה מסוימת בתיבת הדוא''ל של החתול שלו, אבל הוא איבד את שלוות נפשו כשציינו זאת בפניו. | |
|
|
|
|
|
||
|
||||
|
כחלב לתינוק, כיו"ד-גימ"ל עיקרים לאורי פז, כהייזנברג לשרדינגר - דיון 1177, דיון 1178, דיון 1179, דיון 1180 (למען הדורות הבאים). | |
|
|
|
|
|
||
|
||||
|
גם לו היה ביכולתי ללנקק, מוטב היה לו הייתי נמנע מכך ולו בשביל התגובה המשובחת הזאת. | |
|
|
|
|
|
||
|
||||
|
האם לטענה 2+2=10 יש ערך אמת? 1 האם יש לה ערך אמת כאשר פעולת החיבור והמספרים מוגדרים "כמו באריתמטיקה" ובבסיס 10 הרגיל וסימן השוויון מתייחס לפעולת השוויון המקובלת? 2 (הגדרה לא פורמלית להחריד, כמובן) 1 אינטואיטיבית הייתי עונה כאן שיש לטענה ערך אמת, ושהיא שקרית. 2 לאחר ההצגה הזו הייתי עונה שהטענה החדשה והמדוייקת יותר היא שקרית. אבל יכול להיות שהטענה המקורית היתה נכונה, עם משמעות אחרת לסימונים - לדוגמה: בספירה לפי בסיס 4 היא היתה נכונה. או אולי בסימון שבו '=' מסמל "שונה". הטענה של אלון דיברה גם על משפטים שיכולים להיות יותר מורכבים. דוגמה דבילית: "כל מספר שמתחלק בעשר הוא גם זוגי". נתעלם לרגע מהעובדה שיש לזה הוכחה טריוויאלית (אם זה לא נובע ישירות מההגדרה). המשפט הזה יכול להיות נכון או לא נכון. אם קיים ולו מספר סורר אחד שמתחלק בעשר אך אינו זוגי, כל הטענה שגויה. אינטואיטיבית כל אחת מהטענות העצמאיות (לכל מספר שמתחלק בעשר) יכולה להיות נכונה או לא נכונה. ולכן הצירוף של כולן (נכונות הטענה הכללית) נקבע מרגע שקבענו את המערכת. אני חושב עכשיו תורי לשאול אם לא כתבתי יותר מדי שטויות. |
|
|
|
|
|
|
||
|
||||
|
השאלה כמובן איננה האם *קיים* משפט עם ערך אמת, אלא האם *לכל* משפט יש ערך כזה. גדל הראה לנו שקיימים משפטים "לא כריעים". אלון טוען שלמשפט "יש ערך אמת" גם אם אינו כריע, ואני העליתי סברה שהבעייתיות בטענה של אלון טמונה ב"עובדה" שהמושג "יש" לא מוגדר היטב מתמטית. קיבלתי על הראש מגדי, ולאור בורותי ולאור בקיאותו, והגם שלא הצלחתי להחכים נסתתמו טענותי. |
|
|
|
|
|
|
||
|
||||
|
מה זה "לא כריע" לדעתך? מה שגדל הראה הוא שעבור מערכת אקסיומות מסויימת (שמקיימת בלה בלה בלה) יש משפט שלא ניתן להוכיח ממנה. כלומר, אין סדרת סימבולים שמקיימת כללי גזירה צורניים כלשהם שמתאימים למערכת האקסיומות ומסתיימת במשפט של גדל. אלא מה, במערכת אקסיומות טיפה יותר חזקה, שכוללת את המשפט הזה כאקסיומה, דווקא אפשר בלי בעיה להוכיח אותו, ואז גדל נאלץ לבנות משפט אחר. אז כאמור, "לא כריע" זו לא תכונה אינהרנטית של המשפט. זו תוצאה של חולשת מערכת הוכחה מסויימת - ומה שאלון שואל, אם הבנתי אותו נכון, כלל לא קשור למערכת הוכחה זו או אחרת, אלא רק ל*שפה* (הכלי שבו אנו משתמשים כדי לתאר משפטים). |
|
|
|
|
|
|
||
|
||||
|
דרך אחרת לנסח את "לכל משפט יש ערך אמת" היא: "לא קיים משפט שאין לו ערך אמת". אני מחפש לפחות משפט כזה שאין לו ערך אמת. אם אוכל למצוא משפט כזה, ברור שהטענה של אלון שגויה. ולחילופין: אם אצליח להשתכנע שלא קיים משפט כזה, אשתכנע שהטענה של אלון נכונה. מה בדיוק הקשר בין "לא כריע" ל־"לא נכון"? יכול להיות שיש משפט שהוא באמת נכון (או באמת לא נכון). סתם קשה לנו להוכיח את זה. לדוגמה: אני לא מאמין לטענה שכל מספר שמתחלק בעשר הוא זוגי. לכן אני מחליט לעבור על כל המספרים ולבדוק. לצערי הזמן שעומד לרשותי הוא סופי. ולכן לא אצליח לעבור על כל המספרים האפשריים. לכן אף פעם לא אצליח לשכנע את עצמי בדרך זו שהטענה נכונה. האם זה אומר שהטענה שגויה? (אני בכוונה רוצה להשתמש בדוגמאות פשוטות כשאפשר, כדי למנוע מהדיון לרחף בעננים) דוגמה אחרת: בעיית העצירה [ויקיפדיה]. אנחנו רוצים למצוא האם בהנתן תוכנית מחשב וקלט בשבילה, היא תעצור על הקלט. מן המפורסמות היא שאין לבעיה הזו פתרון כללי: אנחנו לא יודעים לבנות תוכנית מחשב שתיתן את התשובה. הבעיה אינה כריעה. אבל די ברור שתשובה קיימת: או שהמכונה עוצרת על הקלט, או שהיא ממשיכה לרוץ לנצח. בדיוק אחת משתי האפשרויות הללו נכונה. |
|
|
|
|
|
|
||
|
||||
|
אם לא הצלחת להחכים הרי שעשינו עבודה גרועה. כפ שציין גדי, אין משפטים לא כריעים. עבור כל מערכת יש משפטים שאינם כריעים בה, אבל כל משפט כריע במערכת מתאימה. השאלה אם יש מערכת *סבירה* שבה משפט נתון הוא יכיח היא מעניינת, אבל לא אותי (כרגע, בפתיל הזה). השאלה שלי היא אחרת. האם יש פסוק "פשוט" שאין לו ערך אמת? כאן "פשוט" הוא קיצור למושג פורמלי (פסוק בשפה מסדר ראשון של האריתמטיקה) המייצג דבר באמת פשוט: טענה המדברת על מספרים טבעיים (ולא קבוצות-של-טבעיים) ומשתמשת בפעולות חיבור וכפל ובכמתים הרגילים, "לכל" ו-"קיים". אני (באמת) לא מכיר מועמד טוב לפסוק שכזה, והנימוקים שאני מכיר לטובת קיומו לוקים בעיני. נימוק אחד אומר שיש פסוקים כאלה שאינם כריעים ב-ZFC אם ZFC עקבית. ואני אומר: בוודאי שיש - למשל, הפסוק (Con(ZFC, או הפסוק "למשוואה הדיופנטית ... אין פתרון" עבור משוואה מחוכמת מסויימת המותאמת ל-ZFC. אני חושב שרוב האנשים דווקא חושבים שאו ש-ZFC עקבית, או שהיא לא עקבית. מדוע צריך להניח שהיא לא-זה-ולא-זה, רק בגלל שבמערכת סטנדרטית מסויימת (במקרה זה, היא עצמה) לא ניתן (כנראה) להוכיח שהיא כן? בעיני גם סביר להניח שאו למשוואה הדיופנטית ההיא יש פתרון, או שאין לה. (אם ZFC עקבית אז אין לה, אגב.) אם נראה לך שיש משוואות דיופנטיות עבורן זה לא נכון ולא לא-נכון שיש פתרון, אתה יכול להסביר למה? אם היינו משוחחים בכל קונטקסט מתמטי אחר, השאלה הזו בכלל לא היתה עולה. איכשהו כשמתחילים לדבר על לוגיקה מתמטית יש נטייה לאבד ביטחון במושגים הטבעיים ביותר, כנראה קצת בגלל משפט גדל (ויותר מזה, פרשנויות לא מדוייקות שלו). אני לא חושב שזה מוצדק. |
|
|
|
|
|
|
||
|
||||
|
אם חושבים על זה, אני בעצם לא מבין כלום. למה התביעה שלך שיהיה מדובר על לוגיקה מסדר ראשון דווקא? יש דוגמאות למשפטים שהם במובהק בלי ערך אמת בטבעיים בלוגיקה מסדר שני? | |
|
|
|
|
|
||
|
||||
|
אם מתחילים לדבר על תת-קבוצות שרירותיות של קבוצות אינסופיות (כמו למשל בשפה מסדר שני של האריתמטיקה), אני חושב שיש יותר הצדקה לספקנות. זה לא לגמרי ברור מה זה "קבוצה שרירותית של טבעיים", וודאי שזה מושג הנמצא הרחק מחוץ להישג ידו של כל אלגוריתם. השערת הרצף, למשל, ניתנת לניסוח כטענה על קבוצות חלקיות של הטבעיים. האם יש לה ערך אמת? הדיעות חלוקות והפעם אני מבין את הסיבות. יש אנשים חריפים מאוד ובקיאים מאוד המשוכנעים לגמרי שזו שאלה חד-משמעית, ויש אחרים חריפים ובקיאים לא פחות המשוכנעים שההיפך הוא הנכון. אני לא לגמרי בטוח מה דעתי. |
|
|
|
|
|
|
||
|
||||
|
יש חריפים ובקיאים שחושבים ככה וחריפים ובקיאים החושבים אחרת, במתמטיקה, כאשר כל העובדות והנגזר מהן ידועים? זה די מטריד אותי. האם אין דרך לעשות דה-לגיטימציה לאנשי אחד המחנות? |
|
|
|
|
|
|
||
|
||||
|
ראשית, לא כל העובדות ידועות. אולי יש מערכת של אקסיומות סבירות מהן נובעת השערת הרצף או שלילתה; הסיכוי לכך (במובן מתאים של "סיכוי") די נמוך אבל מי יודע. בינתיים יש לנו ידיעה חלקית ומכאן ואילך זו כבר פרשנות. שנית, אין חוסר הסכמה על עובדה מתמטית כלשהי, עד כמה שאני יודע. הויכוח הוא פילוסופי. שלישית, למה להיות כזה שלילי? אולי יש דרך לעשות רה-הביליטיציה לאנשי אחד המחנות? |
|
|
|
|
|
|
||
|
||||
|
באסוסיאציה חופשית, נזכרתי באמירתו של כלכלן אמריקאי כלשהו בשנות החמישים: We are facing a reverse upward trend.
|
|
|
|
|
|
|
||
|
||||
|
א"ל מתמתיקאי, אבל לא הבנתי מה הבעיה. מה רע במשפט המקורי שגדל הוכיח שאין לו ערך אמת בתורת המספרים, "אין מספר שהוא קידוד של הוכחת המשפט הזה"1? נכון, יש לו ערך אמת חיובי אם תוסיף לתורת המספרים את המשפט כאקסיומה, אבל באותה מידה אתה גם יכול להוסיף את שלילת המשפט באקסיומה (ואז יש מספר כזה, פשוט לא מספר טבעי). נכון שהראשון פשוט ואינטואיטיבי יותר עבורנו, אבל מי יגיד שהוא נכון יותר? 1 יש מצב שהוספתי או השמטתי שלילה או שתיים. |
|
|
|
|
|
|
||
|
||||
|
צריך להיות זהירים מאוד כאן. מה זה אומר "ערך אמת בתורת המספרים"? תורת המספרים היא תורה מתמטית - אוסף של אקסיומות שמהם אפשר לגזור משפטים. אין משמעות לדיבור על "ערך אמת" של משפט בתורה הזו, אלא לדיבור על האם המשפט יכיח או לא יכיח בתורה הזו. ההקשר שבו מדברים על ערך אמת של משפטים הוא ביחס למודלים השונים והמשונים שיש לתורות שלנו. למשל, הטבעיים הם מודל אחד אפשרי של תורת המספרים. כל עוד אנחנו עוסקים בלוגיקה מסדר ראשון יש לנו את משפט *השלמות* של גדל, לפיו אם משפט כלשהו הוא בעל ערך אמת *בכל המודלים* של התורה שלנו, אז הוא יכיח ממנה, ואז, במובן הזה, יש זהות בין "בעל ערך אמת חיובי" ובין "יכיח". אבל ייתכן מאוד שלתורה שלנו שני מודלים שונים עקרונית, שבאחד מהם המשפט נכון ובשני הוא אינו נכון. זו גם הסיטואציה שמתרחשת במשפט אי השלמות של גדל. במילים אחרות - המשפט של גדל הוא נכון לגמרי במודל של המספרים הטבעיים; אבל מה שגדל מראה הוא שבהכרח לתורת המספרים קיים עוד מודל, לא סטנדרטי, שבו המשפט אינו נכון. |
|
|
|
|
|
|
||
|
||||
|
תודה, זה בדיוק מה שניסיתי להגיד. | |
|
|
|
|
|
||
|
||||
|
מצד אחד, תחת כל מערכת אקסיומות, משפט נתון אולי אמיתי, אולי שקרי ואולי הוא בלתי תלוי בהן. מצד שני אפשר ממש לבנות את המספרים הטבעיים, אחד אחרי השני - וכך אם המשפט מסדר ראשון ומדבר על מספרים - אפשר גם בקלות לבדוק אם יש לו דוגמא נגדית, או אין לו דוגמא נגדית. במובן הזה לא יכול להיות שהוא בלתי תלוי במערכת האקסיומות. |
|
|
|
|
|
|
||
|
||||
|
תוכל לבדוק לי בקלות אם יש או אין דוגמה נגדית להשערת גולדבך? | |
|
|
|
|
|
||
|
||||
|
ברור. אבל זה יקח זמן. | |
|
|
|
|
|
||
|
||||
|
יש הבדל בין ''יקח זמן'' ל''יקח אינסוף זמן''. אם זה יקח אינסוף זמן, אז אי-אפשר לעשות את זה. | |
|
|
|
|
|
||
|
||||
|
אם יש דוגמה נגדית, זה יקח זמן. מה יקרה אם אין? | |
|
|
|
|
|
||
|
||||
|
זו כבר שאלה לפיזיקאים. אבל עצם העובדה ש-*ייתכן* שביקום שלנו (או ביקום אחר) מסע בזמן הוא אפשרי (או שאפשר לעשות דברים דומים כמו ב-תגובה 81101) מעידה על כך שמתמטית זה לא משנה. לא ייתכן שתוצאה לוגית תלויה בטכנולוגיה. | |
|
|
|
|
|
||
|
||||
|
תוצאות לוגיות החלט תלויות בטכנולוגיה. אם תחמם יותר מדי את הרכיב הלוגי1, תוכל לגרום לו לעשות שגיאות. יש לא מעט אנשים (גם בארץ) שמחקרם כולל עינויים דומים של רכיבים לוגיים, כדי לגרום להם לגלות סודות. למרבה הצער אחוזי התמותה (של הרכיבים) יכולים להיות גבוהים למדי. 1 כמו סטודנטים רבים אחרים במדעי המחשב (לפחות בטכניון) למדתי באותו הסימסטר את הקורסים "לוגיקה למדעי המחשב א"' (קורס שמדבר על לוגיקה מתמטית [ויקיפדיה]) ואת הקורס "תכן לוגי" (שמדבר על שער לוגי [ויקיפדיה], או ליתר דיוק רכיבים עם הרבה שערים לוגיים). אף לא אחד משניהם הוא אותה לגיקה שאמורה להיות טריוויאלית (כלומר חלק מהטריוויום [ויקיפדיה]). |
|
|
|
|
|
|
||
|
||||
|
אני למדתי רק מתמטיקה. אולי בגלל זה לא נראה לי שמה שכתבת קשור לדיון הנוכחי. | |
|
|
|
|
|
||
|
||||
|
יש לי הרגשה שמה שניסיתי להסביר (ולא להוכיח) בתגובה 541743 הוא מה שאתה(?) מנסה להראות כאן: גם אם לא נטרח בעצמנו לבדוק את הערך, הערך קיים. הוא נקבע חד־משמעית ע"י תנאי המערכת. | |
|
|
|
|
|
||
|
||||
|
לא הבנתי מה ניסית להגיד כאן, ובפרט איך מסע בזמן קשור. השורה התחתונה היא שאם השערת גולדבך נכונה, לעולם לא נוכל למצוא דוגמה נגדית, ולכן אם כל מה שנעשה הוא לעבור מספר מספר ולחפש דוגמה נגדית לא נוכל אף פעם לעצור ולהגיד ''טוב, השערת גולדבך נכונה'', גם אם יש לנו מסע בזמן. | |
|
|
|
|
|
||
|
||||
|
עם מסע בזמן אפשר לעבור על *כל* המספרים ולקבל תשובה במה שנראה לנו כמו "זמן סופי". | |
|
|
|
|
|
||
|
||||
|
איך אתה זוכר באיזה מספר אתה נמצא? נראה לי שהחל מאיזשהו מספר אסטרונומי מסויים, עצם הפעולה של "המעבר למספר הבא" תארך יותר ממשך חייו של אדם בודד. |
|
|
|
|
|
|
||
|
||||
|
הסבר פרט נמק והדגם. | |
|
|
|
|
|
||
|
||||
|
נאמר שנתון מכשיר שמקבל קלט, מבצע פעולת חישוב, ושולח את הפלט לזמן שלפני תחילת פעילותו. נאמר שהפלט מקדד זוג סדור <ביט, מספר-טבעי> כאשר הביט מקדד את התשובה לשאלה "המספר הוא דוגמא נגדית להשערה". המכשיר לוקח את הפלט, מעלה המספר באחד, וקורא לעצמו שוב - עד אשר הוא מקבל תשובה נגדית. מה יקרה כאשר תפעיל את המכשיר? (יש בעיה קלה עם הקידוד, אבל גם היא "טכנולוגית". תניח שיש קסם, תוצאה ממכניקת הקוונטים, שמאפשרת לקודד את כל המספרים הטבעיים. ואם כבר יש מסע בזמן, אפשר כנראה גם למצוא פתרונות קידוד ללא צודך בקסמים נוספים). כנראה שאפשר לחשוב על עוד פתרונות, תחת הנחות פיזיקליות שונות. |
|
|
|
|
|
|
||
|
||||
|
אני מסכים - מודל חישובי כזה יכול להכריע את השערת גולדבך באופן הזה, ולמעשה יכול להכריע כל שפה ב-RE. אבל מה על שפות שאינן ב-RE? ובאופן יותר ציורי (ולא מדויק לגמרי) - מה עם השערת קולאץ? | |
|
|
|
|
|
||
|
||||
|
גם עם מסע בזמן אי אפשר לעבור על *כל* המספרים כי אינסוף ישאר אינסוף גם בעוד מיליון שנה וגם בעוד מיליארד שנה. | |
|
|
|
|
|
||
|
||||
|
נראה לי שהרעיון הוא כזה, אתה מבקש מחברך הטוב ת'ור לעבור על כל המספרים ואם הוא מגיע למספר שמקיים את התנאי אזי בעזרת הדלוריאן הוא יחזור לשבוע מהיום ויגיד לך שהוא מצא. לכן כל מה שאתה צריך לעשות הוא לחכות שבוע ואז להסתכל אם הוא בא. | |
|
|
|
|
|
||
|
||||
|
יפה! אבל מה עושים עם בעיה טיפה יותר מאתגרת מגולדבך? נניח, השערת קולאץ? |
|
|
|
|
|
|
||
|
||||
|
בשביל זה ת'ור יאלץ לעבוד קצת יותר קשה. עבור כל מספר טבעי (יש לו זמן), הוא יבצע את השלב הראשון. אם התוצאה היא אחד, הוא ישמיט אותו מרשימת המטלות. אחרת, הוא יבצע בו את השלב הבא (כאמור, אחד אחד, לפני הסדר). אם בשלב כל שהוא "יגמרו" המספרים או תתקבל לולאה שונה מאחד (גם חוקיות מספיקה; הוא גם זוכר מה היה בעבר), הוא ידווח דקה אחרי שנשלח. אם הוא נכנס ללולאה אינסופית בלי חוקיות, הוא ימשיך עד שהיא תיפתר. מכאן שהעדר דיווח פירושו שישנן לולאות כאלו (וגם זה סוג של פתרון לבעיה). |
|
|
|
|
|
|
||
|
||||
|
אני חושש שלא הבנתי. באיזה שלב אני (לא ת'ור) אוכל להגיד "בודאות, השערת קולאץ נכונה"? | |
|
|
|
|
|
||
|
||||
|
כעבור דקה, בהתאם לתשובה שת'ור מסר לך (בדקתי את כולם והיא נכונה או בדקתי מספיק כדי למצוא דוגמה מפריכה). אם ת'ור לא מוסר לך כלום, אתה יודע שישנו מקרה של רצף אינסופי ולא מחזורי (ולכן ההשערה לא נכונה). | |
|
|
|
|
|
||
|
||||
|
סליחה, במקרה הראשון הוא כמובן לא חוזר. לא חשוב. | |
|
|
|
|
|
||
|
||||
|
טעיתי קודם, אבל אולי זה יעבוד: ת'ור רושם על פיסת נייר בעיפרון את התשובה. הוא מתחיל מהמספר אחד ומתקדם לאיטו לפי האלגוריתם. כל פעם שהוא מצליח להגיע לאחד, הוא חוזר בזמן ורושם "נכונה". כל פעם שהוא מתחיל מספר חדש, הוא חוזר ורושם "שגויה". אתה מביט בפיסת הנייר דקה לאחר שקראת לו ורואה האם ההשערה נכונה. |
|
|
|
|
|
|
||
|
||||
|
לי זה נראה כמו אחד מהפרדוקסים הללו, כמו הנורה שמכבים ומדליקים בקצב הולך וגדל ואז לא ברור מה קורה כעבור שניה. על פניו, הנייר יזפזפ שוב ושוב בין ''נכונה'' ו''שגויה'', מבלי להגיע לתוצאה חד משמעית. | |
|
|
|
|
|
||
|
||||
|
ההבדל הוא שאת כל הרישומים הוא עושה דקה לפני שאתה מביט בנייר. אבל אני כמובן מסכים. |
|
|
|
|
|
|
||
|
||||
|
אני לא חושב שזה הבדל (כי גם בסיפור המנורה אפשר להסתכל במנורה דקה אחרי שהזפזופים ''נגמרו''). בקיצור, לא השתכנעתי שהשיטה הזו אכן עובדת (אבל כן השתכנעתי, בפעם המי יודע כמה, שמסע בזמן לא אפשרי לוגית). | |
|
|
|
|
|
||
|
||||
|
אנסה פעם נוספת. נתאר לעצמנו שמישהו יוכיח ש (A) במערכת שמקיימת <בלה בלה טבעיים> קיימות טענות (משפטים מסדר ראשון) שלא רק אינן יכיחות (בתוך המערכת המסוימת), אלא אינן ניתנות לידיעה1. אין צורך להביא טענה ספציפית כזו - ההוכחה לא צריכה להיות קונסטרוקטיבית או משהו. לכאורה קשה להבין איך אפשר להוכיח דבר כזה, אבל מצד שני קשה גם להבין (עד שרואים את ההוכחה) איך אפשר להוכיח שטריסקציה של זוית כלשהי עם מחוגה וסרגל היא בלתי אפשרית. אז בוא רק נתאר לעצמנו מצב בו מישהו הצליח להראות שקיימת טענה (מסדר ראשון וכו' וכו') שלא ניתן *לדעת* אם היא נכונה או לא. עם ההנחה הזו, מה משמעות הטענה "לכל משפט יש ערך אמת" (או השאלה "האם יש לכל משפט ערך אמת")? עכשיו, יש כאן באיזה מקום באתר הזה מאמר מרשים ומחכים שמדבר על פסאודו-מסקנות ממשפטי גדל, ואני מניח שגם ה"נתאר לעצמנו" שפתחתי בו נופל ברשימה, למרות ש"בלתי יכיח" מתקרב בצורה חשודה ל"בלתי ניתן לידיעה" (אני מבין שיש כשל של "זה לא בלתי יכיח, זה רק בלתי יכיח במערכת מסוימת", ולמרות שיש לי כמה שאלות על זה אשאיר אותן בצד בינתיים). אז אתרחק מאמירה שגדל כבר הוכיח את (A), ונדמיין איזה קורט אחר שיוכיח אותה עוד שנה ושבעה חדשים. אז בלי קשר לגדל, לכו בבקשה לקראתי ובואו נניח שמישהו אכן הוכיח את (A). במצב כזה, הדרך היחידה שאני מצליח לפרש את "לכל משפט יש ערך אמת" היא דרך איזה אלוהים שאכן יודע את ערך האמת של כל משפט (מסדר ראשון בלה בלה בלה), אבל מונע בערמומיות מבני תמותה לדעת אותו. כך שעבור אתאיסטים, לא ברור איך יכול "להתקיים" ערך כזה. אם אתם איתי עד כאן, ואם שום דבר ממה שאמרתי אינו שטות איומה ונוראית, אז עבור חילוני, האמירה של אלון "לכל משפט מסדר ראשון בלה בלה בלה יש ערך אמת" מיתּרגם לאמירה "ערך האמת של כל משפט ניתן לידיעה". זו אמירה שלעניות דעתי היא חזקה מאד, ואי אפשר להפריח אותה "סתם" לחלל האויר בלי הוכחה או לפחות נימוק משכנע. נימוקים מסוג "כי אם לא אז העולם יהיה מקום איום ונורא לחיות בו" לא יתקבלו. מקווה שלא טירחנתי יותר מידי, אבל זה גם הקשר לרעש של העץ ביער: אם יש אלוהים, אז מספיק ש*הוא* שומע, וכיוון שהוא שומע הכל אז העץ מרעיש בנופלו. אם אין אלוהים, אז אין מי שיקרא לשינויים בלחץ האויר שאנחנו *מאמינים* שהיו כשהעץ נפל "רעש", ולכן השאלה "איזה קול העץ עושה" פחות טפשית לדעתי מאשר לדעת גדי. 1 הכוונה ל"ערך האמת" שלהן. |
|
|
|
|
|
|
||
|
||||
|
יש לי בעיה חמורה ביותר עם ההנחה שלך שיש טענה ש"אינה ניתנת לידיעה". בראש ובראשונה כי לא ברורה לי המשמעות של "לדעת" בהקשר הזה, ואיך היא מאפשרת קיום טענות בלתי-ניתנות-לידיעה שכאלו. למשל, נניח שהשערת גולדבך היא טענה ש"אינה ניתנת לידיעה כזו". עכשיו באים אלי אריק ובנץ. אריק אומר לי "אני יודע שהשערת גולדבך נכונה". בנץ אומר לי "אני יודע שהשערת גולדבך אינה נכונה". ברור לי שלפחות אחד משניהם מקשקש בקומקום, אבל איך אני יכול לומר ששניהם מקשקשים? בלי מושג פורמלי וקונקרטי של "ידיעה" אין על מה לדבר בכלל - בדיוק כשם שבניות בסרגל ומחוגה מוגדרות היטב מבחינה מתמטית, *ורק בגלל זה* אפשר להוכיח שהן בלתי אפשריות; בדומה, כדי להראות שדברים אינם ניתנים לחישוב הכרחי קודם כל לדבר על מודל קונקרטי של חישוב. לטעמי האישי, אגב, "ידיעה" פירושה "קיים אלגוריתם שמחזיר את התשובה הנכונה". מסיבות טכנית זה גורר שכל טענה כמו גולדבך ניתנת לידיעה באופן תיאורטי (בדיוק עם שטות סטייל אריק ובנץ) ודברים שאי אפשר לדעת תמיד מתייחסים למחלקה אינסופית כלשהי של בעיות - למשל, אי אפשר לדעת, בהינתן תוכנית מחשב, אם היא עוצרת או לא. ברור שבמקרים קונקרטיים מסויימים אפשר לדעת את זה, אבל *באופן כללי* לא ניתן לדעת. אם מקבלים את ההגדרה שלי לידיעה, אז לא - אני עדיין לא מסכים שזה שלא ניתן לדעת דברים מסויימים גורר שלא ניתן לייחס להם ערך אמת. המכונה עוצרת או לא עוצרת, בלי קשר לשאלה אם ביכולתנו לדעת זאת או לא. |
|
|
|
|
|
|
||
|
||||
|
אתה צודק שהטענה "נכונותה של השערת גולדבך אינה ניתנת לידיעה" היא טענה קשה לעיכול. לכן הדגשתי שאין הכרח שאפשר יהיה להחיל את המשפט (המדומה שקורט X יוכיח עוד שנה ורבע) על שום טענה *קונקרטית*. כל מה שהנחתי שקורט יודע להוכיח היא ש*קיימת* טענה שאינה ניתנת לידיעה, לא שטענה מסוימת היא כזו או שניתן לסווג טענה ספציפית כלשהי ככזו. משפטי קיום בעלי אופי זה קיימים וידועים. למעשה, עד כמה שידיעתי מגעת, במשך כעשרים שנה לא היתה שום דוגמה קונקרטית למשפט בלתי כריע (אם טעיתי זה לא מאד רלוונטי לטיעון הכללי) השערת גולדבך יכולה להיות טענה כזו, אבל יתכן שאין כלי שיודע לומר האם היא באמת כזו. כשאריק ובנץ באים אליך, אם לאריק יש הוכחה (נכונה) הרי שהוא הראה ש: א': השערת גולדבך אינה מסוג "השערת קורט" ב': דווקא בנץ מקשקש בקומקום. אם לאף אחד מהם אין הוכחה הרי ששניהם מקשקשים (מה זאת אומרת "אני יודע"? מותר לשאול "איך אתה יודע", ובמתמטיקה, התשובה הלגיטימית היחידה היא "הנה ההוכחה"), והשערת גולדבך יכולה להיות מטיפוס "קורט X" ויכולה לא להיות כזו. לגבי בעית העצירה שאתה וצפריר התייחסתם אליה, אני חושב שזה לא ממש רלוונטי. עד כמה שהבנתי מגעת, מה שטיורינג הראה זה שלא קיים אלגוריתם *כללי* שיודע לומר אם אלגוריתם כלשהו עוצר או לא. זה כשלעצמו לא מוכיח שאי אפשר לדעת אם אלגוריתם *מסוים* עוצר או לא. למעשה, אין סיבה לא לחשוב שלגבי *כל* אלגוריתם ניתן למצוא אם הוא יעצור או לא1, אלא שלא יתכן אלגוריתם *כללי* שיתן תשובה כזו. ה־gedankenexperiment שאני תיארתי מניח שקורט X "הוכיח" שקיים לפחות משפט אחד שאינו ניתן לידיעה, גם אם אינו מצביע על משפט מסוים כזה. אני חושב שהמשפט האחרון שלך הוא בדיוק המקום בו איני מבין. >> אני עדיין לא מסכים שזה שלא ניתן לדעת דברים מסויימים גורר שלא ניתן לייחס להם ערך אמת כשאני קורא את המשפט הזה הוא נקרא לי כטאוטולוגיה פשוטה, בזמן שאתה אומר שהוא פשוט לא נכון. מה זה נקרא "ניתן לייחס לו ערך אמת"? בעולם שלי, "ניתן" זה "מישהו יכול". אם משהו הוא "לא ניתן לידיעה", אז איך "מישהו יכול" לדעת? כאן בדיוק נכנס אלוהים מהדלת הקדמית והעץ ביער מהדלת האחורית (no pun intended). שורה תחתונה: אני מבין את הצהרתו של אלון "לכל משפט מסדר ראשון יש ערך אמת" כ"ניתן לדעת את ערך האמת של כל משפט מסדר ראשון". כאמור, זו אמירה חזקה מאד וקשה לקבל אותה בלי הנמקה. (נדמה לי שזה גם האפיטף של הילברט, אבל לא היו לו מספיק שוליים לרשום את ההוכחה) 1 לפחות עד שמישהו יבוא עם הוכחה שקיים אלגוריתם לגביו אי אפשר לדעת. אם יבוא מישהו כזה, להבנתי הוא יהיה בדיוק ה"קורט X" שלי. |
|
|
|
|
|
|
||
|
||||
|
זכור שהמשפט הלא יכיח של גדל עצמו נבנה באופן קונסטרוקטיבי. זה בכל מקרה לא משנה כלום - אם יש משפט "שלא ניתן לדעת" X, אז אריק ובנץ חוזרים על התעלול שתיארתי עם X. במתמטיקה התשובה ל"איך אתה יודע" היא בהחלט *לא* רק "יש לי הוכחה". זו בדיוק הנקודה שאנחנו מנסים להדגיש שוב ושוב כאן. זו גם הסיבה שאני אומר שעלייך להיות מאוד מדוייק עם ההגדרה שלך למושג "ידיעה". אני חושב שלב העניין הוא במשפט הזה שלך: "מה זה נקרא "ניתן לייחס לו ערך אמת"? בעולם שלי, "ניתן" זה "מישהו יכול". אם משהו הוא "לא ניתן לידיעה", אז איך "מישהו יכול" לדעת?" אני לא טוען שמישהו *ידע* מה ערך האמת של המשפט, אלא רק שזה לא פוסל את קיומו של ערך האמת הזה. ערך אמת של משפט, לטעמי, בכלל לא קשור לידע של אדם זה או אחר. |
|
|
|
|
|
|
||
|
||||
|
קולאץ עדיין השערה?! אני משער שזה מה שקורא כשלא בקיאים במיתולוגיה. זה הרי מן המפורסמות שלאחר שהרקולס הפך לאל הוא נטש את חיי האלימות ריפא את ההידרה והם יצאו לטייל, כעבור כמה מאות בשביל לגוון הם באמת החליטו לבדוק את השערת קולאץ (שאז אמנם נקראה בשם אחר אך זו אכן אותה השערה). והם בדקו אותה בצורה הבאה הרקולס חתך ראש של הידרה ושלח אותו ימינה כל שכל פעם שהוא בודק מספר עוקב בסדרה הוא זז ימינה. אם הוא מגיע לאחד הוא חוזר לשמאלו של הרקולס שבוע לאחר שהוא נשלח (יכולות מסע בזמן הם אחד מהיכולות הפחות ידועות של ראש הידרה). אם הראש חוזר הרקולס וההידרה צועדים צעד קדימה ובודקים את המספר הבא. אם הראש לא חוזר הם קבעו לחזור לאולימפוס בזמננו (ההערכות הכי מאוחרות מדברות על תחילת העשור הזה) ולכתוב שירים. לכן כל מה שצריך לעשות הוא ללכת לאולימפוס ולבדוק אם הם שם. |
|
|
|
|
|
|
||
|
||||
|
איבדתי אותך בפסקה האחרונה - לכאורה הם יעשו אינסוף צעדים, ואז מה? בכל מקרה, נראה לי שתגובה פחות ציורית הייתה יותר ברורה כאן. | |
|
|
|
|
|
||
|
||||
|
יש לנו שלוש צירים x,y וt בזמן 0 גם ההידרה וגם הרקולס נמצאים ב(1,0) הראש של ההידרה נע ימינה ביחידת זמן ומגיע ל (1,1,1) שם הוא מחשב את האיבר הראשון של הסדרה המתחילה ב1 שהוא 1 ולכן הוא חוזר לשמאלו של הרקולס באותו זמן שהוא שלח אותו כלומר ב (1,1-,1) יש ראש של הידרה. באותה דרך אם ההשערה נכונה עד 1-i אז ב (i,0,i) ימצא הרקולס והוא ישלח את ההידרה ימינה לכן ב(i,1,i+1 ) ימצא ראש של הידרה המחשב את האיבר הראשון בסדרה המתחילה ב i מכיוון שi שונה מ1 הוא ימשיך לצעוד ימינה וב (i,2,i+2) יהיה ראש של הידרה והוא יחשב את האיבר השני של הסדרה המתחילה בi כך הוא ממשיך לכן אם לכל איבר בסדרה עד האיבר הk-י לא הגענו ל1 בכל שלישיה מהצורה (i,r,i+r) כאשר r קטן שווה לk יהיה ראש של הידרה המחשב את האיבר הr של הסדרה המתחילה בi אם לסדרה יש אחד באיזשהו מקום אז הוא יחזור לשמאלו של הרקולס ולכן ב(i,-1,i) יהיה ראש של הידרה ולכן הרקולס וההידרה יתקדמו צעד קדימה ויגיעו ל (i+1,0,i+1) אחרת הרקולס וההידרה ילכו לאולימפוס. אם מסתכלים רק על המקומות שy שווה ל0 מקבלים שב (i,i) הרקולס וההידרה נמצאים רק אם כל המספרים עד i מקיימים את התנאי לכן הרקולס וההידרה יחזרו לאולימפוס רק אם ההנחה שקרית. |
|
|
|
|
|
|
||
|
||||
|
אני לא מבין את ''יחזרו לאולימפוס''. זה נראה כאילו אתה הופך את הבעיה לשקולה ל''בדוק האם בוצעו אינסוף צעדים'', ולא ברור איך בודקים את זה. | |
|
|
|
|
|
||
|
||||
|
הם ישתמשו בכוח המיוחד של ההידרה ויחזרו לאולימפוס בזמן שלנו. גם בבעיה המקורית (גולדבך) במובן מסוים בדקת האם נעשו אינסוף צעדים כך שאני לא מבין איזה נקודה נראית לך שונה. |
|
|
|
|
|
|
||
|
||||
|
כי כאן צריך להרכיב את הבדיקה ההיא על מה שכבר קורה, ואני לא רואה את החלקים מתחברים. מילא, נתתם לי תרגיל כיפי בחישוביות. מתישהו אחשוב עליו עד הסוף ואז אוכל להסכים/למצוא דוגמה נגדית משכנעת. רק קצת חבל שהדיון לא יימשך כאן. |
|
|
|
|
|
|
||
|
||||
|
אחלה. השאלה העיקרית היא האם ברור לך שעברת לטענה אחרת?:) (גם אם בפוקס היסטרי הבנת את הבדיחה אתה כמובן לא חייב לענות). |
|
|
|
|
|
|
||
|
||||
|
הבנתי, הבנתי. | |
|
|
|
|
|
||
|
||||
|
הרקולס עונה בזמן סופי על השאלה "האם חישוב נתון יסתיים בזמן סופי" (אם אנחנו יודעים שכן, נוכל לבצע את החישוב בעצמנו בזמן סופי ולקבל את התוצאה). ת'ור: אותו דבר, אך החישוב הנתון יכול לכלול שאלות דומות להרקולס. |
|
|
|
|
|
|
||
|
||||
|
כאמור, אני צריך לראות האם מסתדר לי שת'ור ישאל את הרקולס שאלות, או שיש לנו כאן רמת היררכייה נוספת של מופרכות, וזה משהו שכבר אענה לעצמי עליו בעתיד. | |
|
|
|
|
|
||
|
||||
|
שימוש באינסוף ראשים נוספים נראה לי לא אלגנטי. נראה לי שת'ור היה יכול להסתפק בעזרה מהרקולס1, ולא צריך גם את המדוזה. לכל מספר ת'ור מטיל על הרקולס משימה לחזור ולדווח על ערכו. הרקולס, אגב, יוכל לזהות לולאות (גם אם הן לא כוללות 1). לכן הסיבה היחידה שתמנע מהרקולס לחזור, היא אם הסדרה שמתחילה מהמספר אינה חסומה ותמשיך לגדול לנצח. אם הרקקולס לא חוזר, ת'ור יכול לחזור מייד ולדווח שהטענה אינה נכונה. אם ת'ור לא חוזר ומדווח, הטענה נכונה. 1 במחשבה שניה, אולי עדיף לגייס את סיזיפוס לעזרה במקום את הרקולס? |
|
|
|
|
|
|
||
|
||||
|
1) השערת קולאץ טוענת שכל סדרה תגיע ל1 ולא שכל סדרה חסומה אבל זה נקודה יחסית שולית. 2. הסיבה העיקרית שהשתמשתי בראשי הידרות ובמערכת צירים היא כי רציתי להימנע משתי דמויות זהות באותו זמן ומקום (מה שמוביל לפרדוקסים נוספים). 3. אם הבנתי נכון, אז גם השיטה שלך תעבוד. |
|
|
|
|
|
|
||
|
||||
|
סמיילי שם את הקישור הזה בבלוג שלו. |
|
|
|
|
|
|
||
|
||||
|
סיפור מאד יפה והוא קשור לשאלה מה ניתן להוכיח באמצעים לוגיים. אני לא בטוח שזה הדיון פה כי סך הכל ניסיתי להסביר פה נקודה יחסית טכנית. צריך לשאול את האלמוני למה הוא התכוון. |
|
|
|
|
|
|
||
|
||||
|
אין מספיק אטומים ביקום כדי לכתוב מספרים הדורשים בדיקה. | |
|
|
|
|
|
||
|
||||
|
אלו נימוקים ''משעממים'' ולא רלוונטיים לדיון הזה. | |
|
|
|
|
|
||
|
||||
|
למה סיבוכיות המקום של האלגוריתם פחות מעניינת מסיבוכיות הזמן שלו? | |
|
|
|
|
|
||
|
||||
|
גם סיבוכיות הזמן לא מעניינת. מעניין רק אם צריך זמן אינסופי או לא. טיעונים בסגנון ''הזמן שייקח לאלגוריתם לרוץ ארוך יותר מזמן הקיום של המין האנושי כולו'' לא רלוונטיים. | |
|
|
|
|
|
||
|
||||
|
אם ת'ור יכול לעבור על אינסוף מספרים, בשביל מה הוא צריך דלוריאן למסע בזמן? כל מה שהוא צריך זה לנסוע עד קצה היקום. ונשארה כמובן השאלה איך אני יכול להאמין לו. אחרי מספיק שנים, לוקי ישתחרר מכלאו והוא עלול להתחזות לת'ור. |
|
|
|
|
|
|
||
|
||||
|
לא הבנתי את השאלה הראשונה. לגבי השניה אפשר לתת לת'ור חפץ מזהה. |
|
|
|
|
|
|
||
|
||||
|
אם למשפט אין הוכחה ואין הפרכה, איך מסע בזמן יעזור לך למצוא אחת מאלה בכל-זאת? גם מסע בזמן דורש נקודת יעד סופית. | |
|
|
|
|
|
||
|
||||
|
אנחנו יכולים לדעת שת'ור לא נתקל בשגיאה באף אחד מהמספרים: אם הוא היה נתקל בשגיאה הוא היה (תוך פרק זמן סופי כלשהו) חוזר אחורה ומדווח על כשלון. | |
|
|
|
|
|
||
|
||||
|
אני חושב שנטפלת יותר מהרצוי למילה "יש" או "קיים" (ערך אמת). אני חושב שלאלון לא יהיה אכפת לשנות את נוסח השאלה שלו, ולשאול האם כל משפט הוא נכון או לא-נכון. זה עדיין מחייב אותנו - בוודאי את מי שעונה תשובה חיובית - למושג "נכון", או אם תרצה "ערך אמת", אבל מוציא את העז, הבאמת לא ריחנית, של *קיום* ערך האמת. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |