בתשובה להאייל האלמוני, 28/04/10 21:45
סוף הדרך 541836
נראה לי שהרעיון הוא כזה, אתה מבקש מחברך הטוב ת'ור לעבור על כל המספרים ואם הוא מגיע למספר שמקיים את התנאי אזי בעזרת הדלוריאן הוא יחזור לשבוע מהיום ויגיד לך שהוא מצא. לכן כל מה שאתה צריך לעשות הוא לחכות שבוע ואז להסתכל אם הוא בא.
סוף הדרך 541838
יפה!

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

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

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

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

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

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

עם ההנחה הזו, מה משמעות הטענה "לכל משפט יש ערך אמת" (או השאלה "האם יש לכל משפט ערך אמת")?

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

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

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

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

1 הכוונה ל"ערך האמת" שלהן.
סוף הדרך 541862
יש לי בעיה חמורה ביותר עם ההנחה שלך שיש טענה ש"אינה ניתנת לידיעה". בראש ובראשונה כי לא ברורה לי המשמעות של "לדעת" בהקשר הזה, ואיך היא מאפשרת קיום טענות בלתי-ניתנות-לידיעה שכאלו.

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

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

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

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

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

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

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

אני חושב שהמשפט האחרון שלך הוא בדיוק המקום בו איני מבין.

>> אני עדיין לא מסכים שזה שלא ניתן לדעת דברים מסויימים גורר שלא ניתן לייחס להם ערך אמת

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

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

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

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

אני חושב שלב העניין הוא במשפט הזה שלך:

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

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

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

אם הראש חוזר הרקולס וההידרה צועדים צעד קדימה ובודקים את המספר הבא. אם הראש לא חוזר הם קבעו לחזור לאולימפוס בזמננו (ההערכות הכי מאוחרות מדברות על תחילת העשור הזה) ולכתוב שירים. לכן כל מה שצריך לעשות הוא ללכת לאולימפוס ולבדוק אם הם שם.
סוף הדרך 541879
איבדתי אותך בפסקה האחרונה - לכאורה הם יעשו אינסוף צעדים, ואז מה? בכל מקרה, נראה לי שתגובה פחות ציורית הייתה יותר ברורה כאן.
סוף הדרך 541885
יש לנו שלוש צירים 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 מקיימים את התנאי לכן הרקולס וההידרה יחזרו לאולימפוס רק אם ההנחה שקרית.
סוף הדרך 541892
אני לא מבין את ''יחזרו לאולימפוס''. זה נראה כאילו אתה הופך את הבעיה לשקולה ל''בדוק האם בוצעו אינסוף צעדים'', ולא ברור איך בודקים את זה.
סוף הדרך 541893
הם ישתמשו בכוח המיוחד של ההידרה ויחזרו לאולימפוס בזמן שלנו.
גם בבעיה המקורית (גולדבך) במובן מסוים בדקת האם נעשו אינסוף צעדים כך שאני לא מבין איזה נקודה נראית לך שונה.
סוף הדרך 541894
כי כאן צריך להרכיב את הבדיקה ההיא על מה שכבר קורה, ואני לא רואה את החלקים מתחברים.

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

ת'ור: אותו דבר, אך החישוב הנתון יכול לכלול שאלות דומות להרקולס.
סוף הדרך 541906
כאמור, אני צריך לראות האם מסתדר לי שת'ור ישאל את הרקולס שאלות, או שיש לנו כאן רמת היררכייה נוספת של מופרכות, וזה משהו שכבר אענה לעצמי עליו בעתיד.
סוף הדרך 541897
שימוש באינסוף ראשים נוספים נראה לי לא אלגנטי. נראה לי שת'ור היה יכול להסתפק בעזרה מהרקולס‏1, ולא צריך גם את המדוזה.

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

אם הרקקולס לא חוזר, ת'ור יכול לחזור מייד ולדווח שהטענה אינה נכונה. אם ת'ור לא חוזר ומדווח, הטענה נכונה.

1 במחשבה שניה, אולי עדיף לגייס את סיזיפוס לעזרה במקום את הרקולס?
סוף הדרך 541899
1) השערת קולאץ טוענת שכל סדרה תגיע ל1 ולא שכל סדרה חסומה אבל זה נקודה יחסית שולית.
2. הסיבה העיקרית שהשתמשתי בראשי הידרות ובמערכת צירים היא כי רציתי להימנע משתי דמויות זהות באותו זמן ומקום (מה שמוביל לפרדוקסים נוספים).
3. אם הבנתי נכון, אז גם השיטה שלך תעבוד.
סוף הדרך 541884
סמיילי שם את הקישור הזה בבלוג שלו.
סוף הדרך 541886
סיפור מאד יפה והוא קשור לשאלה מה ניתן להוכיח באמצעים לוגיים.
אני לא בטוח שזה הדיון פה כי סך הכל ניסיתי להסביר פה נקודה יחסית טכנית. צריך לשאול את האלמוני למה הוא התכוון.
סוף הדרך 541839
אין מספיק אטומים ביקום כדי לכתוב מספרים הדורשים בדיקה.
סוף הדרך 541840
אלו נימוקים ''משעממים'' ולא רלוונטיים לדיון הזה.
סוף הדרך 541853
למה סיבוכיות המקום של האלגוריתם פחות מעניינת מסיבוכיות הזמן שלו?
סוף הדרך 541855
גם סיבוכיות הזמן לא מעניינת. מעניין רק אם צריך זמן אינסופי או לא. טיעונים בסגנון ''הזמן שייקח לאלגוריתם לרוץ ארוך יותר מזמן הקיום של המין האנושי כולו'' לא רלוונטיים.
סוף הדרך 541842
אם ת'ור יכול לעבור על אינסוף מספרים, בשביל מה הוא צריך דלוריאן למסע בזמן? כל מה שהוא צריך זה לנסוע עד קצה היקום.

ונשארה כמובן השאלה איך אני יכול להאמין לו. אחרי מספיק שנים, לוקי ישתחרר מכלאו והוא עלול להתחזות לת'ור.
סוף הדרך 541849
לא הבנתי את השאלה הראשונה.

לגבי השניה אפשר לתת לת'ור חפץ מזהה.

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

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