בתשובה לצפריר כהן, 27/04/10 22:27
 |
|
 |
||
|
||||
 |
השאלה כמובן איננה האם *קיים* משפט עם ערך אמת, אלא האם *לכל* משפט יש ערך כזה. גדל הראה לנו שקיימים משפטים "לא כריעים". אלון טוען שלמשפט "יש ערך אמת" גם אם אינו כריע, ואני העליתי סברה שהבעייתיות בטענה של אלון טמונה ב"עובדה" שהמושג "יש" לא מוגדר היטב מתמטית. קיבלתי על הראש מגדי, ולאור בורותי ולאור בקיאותו, והגם שלא הצלחתי להחכים נסתתמו טענותי. |
 |
 |
 |
|
|
|
||
|
||||
|
מה זה "לא כריע" לדעתך? מה שגדל הראה הוא שעבור מערכת אקסיומות מסויימת (שמקיימת בלה בלה בלה) יש משפט שלא ניתן להוכיח ממנה. כלומר, אין סדרת סימבולים שמקיימת כללי גזירה צורניים כלשהם שמתאימים למערכת האקסיומות ומסתיימת במשפט של גדל. אלא מה, במערכת אקסיומות טיפה יותר חזקה, שכוללת את המשפט הזה כאקסיומה, דווקא אפשר בלי בעיה להוכיח אותו, ואז גדל נאלץ לבנות משפט אחר. אז כאמור, "לא כריע" זו לא תכונה אינהרנטית של המשפט. זו תוצאה של חולשת מערכת הוכחה מסויימת - ומה שאלון שואל, אם הבנתי אותו נכון, כלל לא קשור למערכת הוכחה זו או אחרת, אלא רק ל*שפה* (הכלי שבו אנו משתמשים כדי לתאר משפטים). |
|
|
|
|
|
|
||
|
||||
|
דרך אחרת לנסח את "לכל משפט יש ערך אמת" היא: "לא קיים משפט שאין לו ערך אמת". אני מחפש לפחות משפט כזה שאין לו ערך אמת. אם אוכל למצוא משפט כזה, ברור שהטענה של אלון שגויה. ולחילופין: אם אצליח להשתכנע שלא קיים משפט כזה, אשתכנע שהטענה של אלון נכונה. מה בדיוק הקשר בין "לא כריע" ל־"לא נכון"? יכול להיות שיש משפט שהוא באמת נכון (או באמת לא נכון). סתם קשה לנו להוכיח את זה. לדוגמה: אני לא מאמין לטענה שכל מספר שמתחלק בעשר הוא זוגי. לכן אני מחליט לעבור על כל המספרים ולבדוק. לצערי הזמן שעומד לרשותי הוא סופי. ולכן לא אצליח לעבור על כל המספרים האפשריים. לכן אף פעם לא אצליח לשכנע את עצמי בדרך זו שהטענה נכונה. האם זה אומר שהטענה שגויה? (אני בכוונה רוצה להשתמש בדוגמאות פשוטות כשאפשר, כדי למנוע מהדיון לרחף בעננים) דוגמה אחרת: בעיית העצירה [ויקיפדיה]. אנחנו רוצים למצוא האם בהנתן תוכנית מחשב וקלט בשבילה, היא תעצור על הקלט. מן המפורסמות היא שאין לבעיה הזו פתרון כללי: אנחנו לא יודעים לבנות תוכנית מחשב שתיתן את התשובה. הבעיה אינה כריעה. אבל די ברור שתשובה קיימת: או שהמכונה עוצרת על הקלט, או שהיא ממשיכה לרוץ לנצח. בדיוק אחת משתי האפשרויות הללו נכונה. |
|
|
|
|
|
|
||
|
||||
|
אם לא הצלחת להחכים הרי שעשינו עבודה גרועה. כפ שציין גדי, אין משפטים לא כריעים. עבור כל מערכת יש משפטים שאינם כריעים בה, אבל כל משפט כריע במערכת מתאימה. השאלה אם יש מערכת *סבירה* שבה משפט נתון הוא יכיח היא מעניינת, אבל לא אותי (כרגע, בפתיל הזה). השאלה שלי היא אחרת. האם יש פסוק "פשוט" שאין לו ערך אמת? כאן "פשוט" הוא קיצור למושג פורמלי (פסוק בשפה מסדר ראשון של האריתמטיקה) המייצג דבר באמת פשוט: טענה המדברת על מספרים טבעיים (ולא קבוצות-של-טבעיים) ומשתמשת בפעולות חיבור וכפל ובכמתים הרגילים, "לכל" ו-"קיים". אני (באמת) לא מכיר מועמד טוב לפסוק שכזה, והנימוקים שאני מכיר לטובת קיומו לוקים בעיני. נימוק אחד אומר שיש פסוקים כאלה שאינם כריעים ב-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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |