בתשובה לעוזי ו., 03/01/07 23:45
שתי הערות 427721
"*אם* "לוח שחמט הוא..."

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

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

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

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

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

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

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

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

כתבתי כאן הודעה די ארוכה, אבל בסיומה הגעתי למסקנה שאני לא באמת רוצה להגן על העמדה הזאת. נראה, אני צריך לחשוב על זה עוד קצת‏1.
____________
1- בד"כ זה אומר שאף פעם לא אחזור לזה.
שתי הערות 427821
אם אתה מעוניין בספקנות בלבד, בבקשה; כמו שאמרתי קודם, תמיד אפשר לומר "מה אם" על הכל. שנזכיר כאן שהמתמטיקאים עובדים עם מערכת אקסיומות שלא יכולה להוכיח שאין בה סתירה?

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

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

בעולם האמיתי בעית העצירה פתורה, כמובן: כל מימוש פיזיקלי של מכונת טיורינג עוצר בסופו של דבר, גם אם "סופו של דבר" הוא בעוד כמה מיליארד שנים, כשכל היקום יהיה בשיווי משקל תרמודינמי בסביבות האפס המוחלט.
שתי הערות 427913
נכון, אבל בדיבורים כמו ''בעולם האמיתי בעיית העצירה פתורה'' לוקה באותה בעייתיות שאפיינה את הדיון המוקדם יותר שלי עם זה שלא הבין מה השוס הגדול כאן. אולי בעיית העצירה לכשעצמה אינה בעלת עניין מעשי בעולם שלנו, אבל אפשר להוכיח בעזרתה אי כריעות של בעיות שיישארו לא כריעות גם בעולם שלנו, דוגמת בעיית מציאת דרך כללית לפתרון משוואה דיופנטית.
שתי הערות 427916
כמובן. אני בהחלט איתך בקשר לעניין העיקרי, כל עוד אנחנו זוכרים ש"משוואה דיופנטית" היא יצור מתמטי, לא פיזיקלי (גם ביום שישי). הדוגמא היפה שקהלת הביא בקשר לפתרון "משוואות" בעזרת מערכת קפיצים ומשקולות‏1 מבהירה את זה.
_____________
1- וכאן המקום לשאול אם מישהו מכיר את הטופולוגיה של מערכת כבישים מסוימת, לא נורא מסובכת, שבה סלילת כביש נוסף *מגדילה* את זמן הנסיעה הממוצע, למרות שכל נהג ממשיך להתנהג באופן אופטימלי מבחינתו. נתקלתי בזה לפני שנים בירחון Omni, התרשמתי עמוקות, אבל הגליון אבד לי ואני לא מצליח למצוא שום דבר בקשר לזה מאז. הקשר לענייננו: גם שם הדגימו איך זה קורה בעזרת מערכת קפיצים.
שתי הערות 427927
1 לא מכיר, אבל נראה לי כך: אם מהירות הנסיעה בכביש אינה תלויה במספר הנהגים המשתמשים בו, דומני שמערכת כזו לא תיתכן. אם, לעומת זאת, יש במודל גורם של "עומס תנועה", אז נראה שזי די קל: מספיק שיש שני נהגים הבוחרים בכבישים שונים לפני התוספת, אך שניהם בוחרים בכביש החדש כי הוא יותר מהיר עבור כל אחד מהם אישית - וכך שניהם מפסידים בגלל "עומס התנועה" הנוצר בכביש המשותף. קל לממש זאת אם הנהגים מתחילים ממקומות שונים, ואם הכבישים אינם סימטריים (מהירות הנסיעה תלויה בכיוון).
שתי הערות 427933
זה לא נשמע מאוד סביר, אלא רק בהנחה שלרוב המכריע של הנהגים הכביש החדש מתאים יותר.
שתי הערות 427937
עכש''ז המהירות היתה באמת תלויה בעומס, אבל אם ''שניהם מפסידים'' כנראה שכדאי להם, או לפחות לאחד מהם, לחזור ולנסוע בנתיב הישן. זה לא היה המצב במקרה עליו אני מדבר (אולי אם יש יותר משניים כבר צריך קואליציה של כמה נהגים כדי לשפר את המצב, וקואליציה כזאת אינה יציבה כי לכל נהג משתלם לא להיות חלק ממנה. אני עוד מקווה שמישהו מכיר את הסיטואציה וישלח לי קישורית).
שתי הערות 427943
לא בטוח שהבנתי. לנסוע בנתיב הישן ולהתעלם מהחדש אפשר תמיד, ולכן קואליציה הכוללת את כל הנהגים תמיד יכולה להבטיח שמצבה לא יורע. הנחתי שהכוונה היא שהנהגים פועלים בצורה לא קואליציונית (אם יש מגבלות על גודל הקואליציות, השאלה כבר הופכת למלאכותית מדי).
שתי הערות 427950
אתה לא בטוח שהבנת? *אני* לא בטוח שהבנתי!

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

כאמור, אני ממשיך לקוות שמישהו יבוא לעזרתי, שכן אני בטח מקשקש (מה שקורה לי לא מעט לאחרונה, ועם הקהל הסליחה).
שתי הערות 427994
4 נקודות: A B C D. המטרה: להגיע מ-A ל-D.
בין A ו-B יש כביש מהיר אך ארוך שלוקח שעה ללא קשר לנפח התנועה. כנ"ל בין C ו-D. בין B ו-D יש כביש קצר וצר שלוקח זמן פרופורציונלי לנפח התנועה, כך שבמקרה של עומס 1 (נאמר 1000 מכוניו לשעה) לוקח שעה לנסוע בו. כנ"ל בין C ו-D. נניח שהעומס הנוכחי (של מכוניות הרוצות להגיע מ-A ל-D) הוא 1 (דהיינו, 1000 מכוניות לשעה). מצב שיווי המשקל הוא שחצי מהן יסעו דרך B וחצי מהן דרך C. זמן הנסיעה הוא שעה וחצי: שעה בכביש המהיר ועוד חצי שעה בכביש הצר (בכל אחד מהם יש עומס חצי).
כעת, אם יסללו כביש מהיר נפלא בין B ו-C, המצב רק יורע. במקרה הקיצוני, נניח שהכביש החדש לוקח זמן זניח. אז כולם יסעו מ-A ל-C ל-B ול-D. העומס יהיה 1 ולכן הנסיעה כולה תיקח שעתיים.
שתי הערות 427996
לפני שאני מייגע את מוחי, "כנ"ל בין C ו-D" מופיע פעמיים בהסבר שלך. רצית לכתוב A ו-C בפעם השניה? (כלומר צלעות נגדיות במקבילית שלך הן בעלות אותו אפיון תעבורתי?)

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

(למיטב זכרוני הטופולוגיה באותו מקור שנעלם לי היתה טיפה יותר מסובכת. אני זוכר שתמהתי אם ישנם בפועל מקומות בהם מוטב לסגור כביש קיים, ואם מישהו מחפש מקרים כאלה)
שתי הערות 428006
אכן, הכוונה היתה "בין A ן-C".
הנקודה היא שכל הנהגים יסעו דרך שני הכבישים הצרים (AC ו-BD) ובאוטוסטרדה (CB) המקשרת בינהם. כמובן, אם העומס יגדל מעבר ל-‏1, חלקם יעברו לכבישים המהירים.
שתי הערות 429629
נכון!!!
כל עוד זמן הנסיעה בכבישים הצרים הוא פחות מ-‏1, משתלם לכל נהג ליסוע דרכם. אכן מפתיע.
ללמדכם שלא תמיד אפשר לסמוך על "ידיים נעלמות"!!
שתי הערות 428007
"למיטב זכרוני הטופולוגיה באותו מקור שנעלם לי היתה טיפה יותר מסובכת".
אתה מתכוון שהרעיון התייחס למערכת כבישים מסוימת, לא לכל מצב שבו יש כביש חדש?
שתי הערות 428013
כמובן.

(אתה מתלוצץ?)
שתי הערות 428018
לא, ואתה?
מהתגובה המקורית שבה תיארת את העניין קיבלתי רושם שמדובר ב*כל* מצב של כביש חדש.
שתי הערות 428020
אבוי, אם כך הניסוח שלי לקה בחסר גדול. ברור שאם כל כביש חדש היה גורם הרעה היינו במצב פרדוקסלי עד אימה.
שתי הערות 428026
נא לא להיבהל בטרם עת. ייתכן בהחלט שהבנתי היא שלקתה בחסר גדול: אני פשוט מתעצלת לחפש את הנוסח ההוא.:)
שתי הערות 428029
תגובה 427916

("טופולגיה של מערכת כבישים *מסוימת*" (הדגשה לא במקור))
שתי הערות 428035
אכן. מדובר בהבנתי הלקויה.
שתי הערות 428008
יש מצבים שבהם אין קשר בין זמן הנסיעה לנפח התנועה?
שתי הערות 428014
ודאי שיש מצבים כאלה, כאשר רק חלק קטן מקיבולת הכביש מנוצל.
שתי הערות 428019
גם אז הזמן תלוי בעובדה שרק חלק קטן מהקיבולת מנוצל. כלומר, אם במקרה הקיבולת תנצל במלואה ולמעלה מזה, זמן הנסיעה ישתנה, לא?
שתי הערות 428025
כן. אבל יש מצבים בהם אתה רשאי להניח שנפח התנועה קטן, כך שתוספת מכוניות לא תשפיע על זמן הנסיעה (לדוגמא: כביש צר שהוא המקור היחיד לכביש רחב יותר בהמשך. הכביש הרחב לעולם לא יהיה עמוס באופן בעייתי).

אגב, אותו דבר נכון לרשתות תקשורת מחשבים.
שתי הערות 428032
יש בזה משהו.
שתי הערות 428114
שתי הערות 428120
תודה!

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

"In 1983 Steinberg and Zangwill provided, under reasonable assumptions, necessary and sufficient conditions for Braess' paradox to occur in a general transportation network when a new route is added. As a corollary, they obtain that Braess' paradox is about as likely to occur as not occur; their result applies to random rather than planned networks and additions."

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

אגב, בעניין משיק: ככרות התנועה המתרבות שנחשבות להצלחה גדולה מהוות, לפעמים, מפגע תחבורתי. כאשר עומסי התנועה אינם סימטריים (ובהרבה מקומות זה בדיוק מה שקורה בשעות העומס) נוצר יתרון עצום לבאים מהדרך הסמוכה מימין לזאת שאין בה עומס.
שתי הערות 428122
מכיר 802.5?
שתי הערות 428126
IEEE 802.5 ? לא.
שתי הערות 428131
זה מזכיר קצת כיכר.
שתי הערות 428137
נכון. אני לא מכיר מספיק את הפרוטוקול כדי לדעת אם מחשב אחד יכול להשתלט על התעבורה (כאשר האסימון אצלו ויש לו הודעות להפיץ, הוא לא נותן צ'אנס לאחרים), אבל אני מניח שההתנהגות הטיפוסית יותר ידידותית מזו של נהגים שרוצים להגיע לעבודה בבוקר. ובכלל, נדמה לי ש token ring הולך ומאבד פופולריות לטובת ethernet שבעיותיו מתמעטות ברשתות מהירות עם מתג חכם (רמזור?). אולי לזה כיוונת.
שתי הערות 428147
עכש''י האסימון מאפשר לבעליו לשלוח רק מספר מוגבל של הודעות.
אגב, רמזור הוא לא יעיל בשל זמני האיתחול ( עד שהמכונית הראשונה יוצאת לדרך) והצורך לוודא שכל המכוניות בכיוון המאונך גמרו לגנוב את האדום לפני שהירוק מופיע.
שתי הערות 428148
הצורך לוודא שכל המכוניות בכיוון המאונך גמרו לגנוב את האדום לפני שהירוק מופיע הוא צורך מדומה, ולמעשה אינו קיים.
החוק אוסר כניסה לצומת כאשר האור ברמזור שונה מירוק‏1, ומן הצד השני, גם כאשר האור ברמזור ירוק, החוק אוסר להיכנס לצומת אם אינו פנוי.
הזמן המת המיועד כביכול לוודא שכל המכוניות בכיוון המאונך גמרו לגנוב את האדום לפני שהירוק מופיע הוא זה שיוצר את התופעה.

__
1 או, בתנאים מגבילים, צהוב מהבהב, אבל לא זה המקרה.
שתי הערות 428150
חוק? אני מבין שאדוני כותב מאירופה.
שתי הערות 428140
מויקי הגעתי גם לאתר שמראה את ההקבלה למערכת פשוטה של קפיצים: http://www.davros.org/science/roadparadox.html

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

יזם זריז שבונה כביש בין הנקודות A ו-B עולה על כשל של היד הנעלמה.
שתי הערות 428155
"יזם זריז שבונה כביש בין הנקודות A ו-B עולה על כשל של היד הנעלמה".
זה לא כל כך מתקבל על הדעת. הוא לא יודע מי העובדים שלו? הוא לא יודע של מי הידיים?
שתי הערות 428157
הידיים ויתר השלד הם של ספק-יהודים, לכן צריך לעצור את העבודות ולהעתיק את הקברים.
שתי הערות 428164
הממם. אני מדמיין לעצמי אגודת סתרים של מהנדסי תחבורה חרדים-ליטאים האמונים על תורתו של Braess, הנפגשים בבתי מדרש בבני-ברק פעם בחצי שנה מול מפות כבישים מפורטות ומתכננים ביחד איך, בעזרת אתי-חפירה, כמה עצמות חמור, ובעיקר עוז-רוח, להציל את מדינת ישראל שוב-שוב מאסון תעבורתי מעשי ידיה-עצמה...
שתי הערות 428167
חסידי בראס-לב
שתי הערות 428174
או בקיצור, בראס-בנד.
שתי הערות 552091
סרטון וידיאו באורך שעה: http://mitworld.mit.edu/video/812
שתי הערות 427947
לא ממש. שינית כאן קצת את ההגדרה של "מכונת טיורינג עוצרת", כי המשמעות המקורית היא "עוצרת עם פלט מתאים לגבי הבעיה", ואצלך המשמעות היא "עוצרת כנ"ל או לחלופין מושמדת/חדלה להתקיים".
שתי הערות 427951
נראה לי שהכוונה הייתה שבעיית העצירה ''פתורה'' עבור תת המחלקה של מכונות הטיורינג שניתנות למימוש במציאות.
חרמפפפ. 427953
שתי הערות 427952
ההערה שלך נכונה למדי, אם כח להגנתי אטען שלא יהיה מי שיוכל לקבוע אם לא התקבל הפלט המצופה בננו-השניה שלפני הסוף. קלוש למדי, אני מודה.

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

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

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