 |
|
 |
||
|
||||
 |
אם אתה מעוניין בספקנות בלבד, בבקשה; כמו שאמרתי קודם, תמיד אפשר לומר "מה אם" על הכל. שנזכיר כאן שהמתמטיקאים עובדים עם מערכת אקסיומות שלא יכולה להוכיח שאין בה סתירה? הבעיה מתחילה כשהגישה של "אי אפשר להוכיח שום דבר" גורמת לאנשים לחשוב "היי, הבעיה בבעיית העצירה היא בסך הכל שהחבר'ה האלו עובדים עם מודל מיושן כמו מכונת טיורינג! אני *בטוח* שעל הפנטיום החדש שלי אפשר לפתור אותה, אז אני אבזבז חודש בלכתוב תוכנה שעושה את זה!". (מצד שלישי, לרוב האנשים שיאמרו כזה דבר הם בדיוק מהסוג שהיית רוצה שיעזוב אותך במנוחה למשך חודש). |
 |
 |
 |
|
|
|
||
|
||||
|
אני ממש לא נמנה עם האוחזים בדעה שכל ההשערות שקולות כי לא ניתן להוכיח אף אחת מהן. להיפך, הגישה הזאת מעלה אצלי את הסעיף פעם אחר פעם. בעולם האמיתי בעית העצירה פתורה, כמובן: כל מימוש פיזיקלי של מכונת טיורינג עוצר בסופו של דבר, גם אם "סופו של דבר" הוא בעוד כמה מיליארד שנים, כשכל היקום יהיה בשיווי משקל תרמודינמי בסביבות האפס המוחלט. |
|
|
|
|
|
|
||
|
||||
|
נכון, אבל בדיבורים כמו ''בעולם האמיתי בעיית העצירה פתורה'' לוקה באותה בעייתיות שאפיינה את הדיון המוקדם יותר שלי עם זה שלא הבין מה השוס הגדול כאן. אולי בעיית העצירה לכשעצמה אינה בעלת עניין מעשי בעולם שלנו, אבל אפשר להוכיח בעזרתה אי כריעות של בעיות שיישארו לא כריעות גם בעולם שלנו, דוגמת בעיית מציאת דרך כללית לפתרון משוואה דיופנטית. | |
|
|
|
|
|
||
|
||||
|
כמובן. אני בהחלט איתך בקשר לעניין העיקרי, כל עוד אנחנו זוכרים ש"משוואה דיופנטית" היא יצור מתמטי, לא פיזיקלי (גם ביום שישי). הדוגמא היפה שקהלת הביא בקשר לפתרון "משוואות" בעזרת מערכת קפיצים ומשקולות1 מבהירה את זה. _____________ 1- וכאן המקום לשאול אם מישהו מכיר את הטופולוגיה של מערכת כבישים מסוימת, לא נורא מסובכת, שבה סלילת כביש נוסף *מגדילה* את זמן הנסיעה הממוצע, למרות שכל נהג ממשיך להתנהג באופן אופטימלי מבחינתו. נתקלתי בזה לפני שנים בירחון Omni, התרשמתי עמוקות, אבל הגליון אבד לי ואני לא מצליח למצוא שום דבר בקשר לזה מאז. הקשר לענייננו: גם שם הדגימו איך זה קורה בעזרת מערכת קפיצים. |
|
|
|
|
|
|
||
|
||||
|
1 לא מכיר, אבל נראה לי כך: אם מהירות הנסיעה בכביש אינה תלויה במספר הנהגים המשתמשים בו, דומני שמערכת כזו לא תיתכן. אם, לעומת זאת, יש במודל גורם של "עומס תנועה", אז נראה שזי די קל: מספיק שיש שני נהגים הבוחרים בכבישים שונים לפני התוספת, אך שניהם בוחרים בכביש החדש כי הוא יותר מהיר עבור כל אחד מהם אישית - וכך שניהם מפסידים בגלל "עומס התנועה" הנוצר בכביש המשותף. קל לממש זאת אם הנהגים מתחילים ממקומות שונים, ואם הכבישים אינם סימטריים (מהירות הנסיעה תלויה בכיוון). | |
|
|
|
|
|
||
|
||||
|
זה לא נשמע מאוד סביר, אלא רק בהנחה שלרוב המכריע של הנהגים הכביש החדש מתאים יותר. | |
|
|
|
|
|
||
|
||||
|
עכש''ז המהירות היתה באמת תלויה בעומס, אבל אם ''שניהם מפסידים'' כנראה שכדאי להם, או לפחות לאחד מהם, לחזור ולנסוע בנתיב הישן. זה לא היה המצב במקרה עליו אני מדבר (אולי אם יש יותר משניים כבר צריך קואליציה של כמה נהגים כדי לשפר את המצב, וקואליציה כזאת אינה יציבה כי לכל נהג משתלם לא להיות חלק ממנה. אני עוד מקווה שמישהו מכיר את הסיטואציה וישלח לי קישורית). | |
|
|
|
|
|
||
|
||||
|
לא בטוח שהבנתי. לנסוע בנתיב הישן ולהתעלם מהחדש אפשר תמיד, ולכן קואליציה הכוללת את כל הנהגים תמיד יכולה להבטיח שמצבה לא יורע. הנחתי שהכוונה היא שהנהגים פועלים בצורה לא קואליציונית (אם יש מגבלות על גודל הקואליציות, השאלה כבר הופכת למלאכותית מדי). | |
|
|
|
|
|
||
|
||||
|
אתה לא בטוח שהבנת? *אני* לא בטוח שהבנתי! הרעיון שאני מנסה לגלגל הוא שבמצב החדש יש יתרון לנהג בודד (או לקבוצה קטנה) שיבחר בכביש החדש, אבל זה גורם להרעה בתנאים של אלה שלא בוחרים אותו נתיב, לכן עוד ועוד יעברו אליו, והסה"כ יהיה בכל-זאת יותר גרוע מהמצב הקודם. זה יכול לקרות, אולי, אם הכביש החדש מוליך לנתיב אחר, צואר בקבוק כזה, שדרכו עוברים גם אלה שלא נוסעים בחדש. כאמור, אני ממשיך לקוות שמישהו יבוא לעזרתי, שכן אני בטח מקשקש (מה שקורה לי לא מעט לאחרונה, ועם הקהל הסליחה). |
|
|
|
|
|
|
||
|
||||
|
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 ולכן הנסיעה כולה תיקח שעתיים. |
|
|
|
|
|
|
||
|
||||
|
לפני שאני מייגע את מוחי, "כנ"ל בין C ו-D" מופיע פעמיים בהסבר שלך. רצית לכתוב A ו-C בפעם השניה? (כלומר צלעות נגדיות במקבילית שלך הן בעלות אותו אפיון תעבורתי?) אחרי שאבין את זה, אצטרך לחשוב למה כל הנהגים יבחרו אותו נתיב, אם בכביש הצר התנועה דלילה ואפשר לגמור אותו בחצי שעה. (למיטב זכרוני הטופולוגיה באותו מקור שנעלם לי היתה טיפה יותר מסובכת. אני זוכר שתמהתי אם ישנם בפועל מקומות בהם מוטב לסגור כביש קיים, ואם מישהו מחפש מקרים כאלה) |
|
|
|
|
|
|
||
|
||||
|
אכן, הכוונה היתה "בין A ן-C". הנקודה היא שכל הנהגים יסעו דרך שני הכבישים הצרים (AC ו-BD) ובאוטוסטרדה (CB) המקשרת בינהם. כמובן, אם העומס יגדל מעבר ל-1, חלקם יעברו לכבישים המהירים. |
|
|
|
|
|
|
||
|
||||
|
נכון!!! כל עוד זמן הנסיעה בכבישים הצרים הוא פחות מ-1, משתלם לכל נהג ליסוע דרכם. אכן מפתיע. ללמדכם שלא תמיד אפשר לסמוך על "ידיים נעלמות"!! |
|
|
|
|
|
|
||
|
||||
|
"למיטב זכרוני הטופולוגיה באותו מקור שנעלם לי היתה טיפה יותר מסובכת". אתה מתכוון שהרעיון התייחס למערכת כבישים מסוימת, לא לכל מצב שבו יש כביש חדש? |
|
|
|
|
|
|
||
|
||||
|
כמובן. (אתה מתלוצץ?) |
|
|
|
|
|
|
||
|
||||
|
לא, ואתה? מהתגובה המקורית שבה תיארת את העניין קיבלתי רושם שמדובר ב*כל* מצב של כביש חדש. |
|
|
|
|
|
|
||
|
||||
|
אבוי, אם כך הניסוח שלי לקה בחסר גדול. ברור שאם כל כביש חדש היה גורם הרעה היינו במצב פרדוקסלי עד אימה. | |
|
|
|
|
|
||
|
||||
|
נא לא להיבהל בטרם עת. ייתכן בהחלט שהבנתי היא שלקתה בחסר גדול: אני פשוט מתעצלת לחפש את הנוסח ההוא.:) | |
|
|
|
|
|
||
|
||||
|
תגובה 427916 ("טופולגיה של מערכת כבישים *מסוימת*" (הדגשה לא במקור)) |
|
|
|
|
|
|
||
|
||||
|
אכן. מדובר בהבנתי הלקויה. | |
|
|
|
|
|
||
|
||||
|
יש מצבים שבהם אין קשר בין זמן הנסיעה לנפח התנועה? | |
|
|
|
|
|
||
|
||||
|
ודאי שיש מצבים כאלה, כאשר רק חלק קטן מקיבולת הכביש מנוצל. | |
|
|
|
|
|
||
|
||||
|
גם אז הזמן תלוי בעובדה שרק חלק קטן מהקיבולת מנוצל. כלומר, אם במקרה הקיבולת תנצל במלואה ולמעלה מזה, זמן הנסיעה ישתנה, לא? | |
|
|
|
|
|
||
|
||||
|
כן. אבל יש מצבים בהם אתה רשאי להניח שנפח התנועה קטן, כך שתוספת מכוניות לא תשפיע על זמן הנסיעה (לדוגמא: כביש צר שהוא המקור היחיד לכביש רחב יותר בהמשך. הכביש הרחב לעולם לא יהיה עמוס באופן בעייתי). אגב, אותו דבר נכון לרשתות תקשורת מחשבים. |
|
|
|
|
|
|
||
|
||||
|
יש בזה משהו. | |
|
|
|
|
|
||
|
||||
|
http://en.wikipedia.org/wiki/Braess'_paradox
|
|
|
|
|
|
|
||
|
||||
|
תודה! אם כך אג"ג עלה בדיוק על הנקודה, למרות שזכרוני טוען אחרת. החלק הכי מדהים בעיני הוא "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." והשאלה שצצה מיד היא אם יש מי שבודק *אילו כבישים כדאי לסגור* כדי לשפר את מצב התחבורה. ללא ספק זה יהיה שוס אמיתי לגלות שסגירת נתיבי איילון תקצר את זמן הנסיעה :-) (אני מנחש שלפני סלילת כביש חדש עושים סימולציות של מצב התנועה לפני ואחרי, כך שמצבים כאלה לא מתעוררים באופן תדיר, לפחות לא במערכות כבישים פשוטות)אגב, בעניין משיק: ככרות התנועה המתרבות שנחשבות להצלחה גדולה מהוות, לפעמים, מפגע תחבורתי. כאשר עומסי התנועה אינם סימטריים (ובהרבה מקומות זה בדיוק מה שקורה בשעות העומס) נוצר יתרון עצום לבאים מהדרך הסמוכה מימין לזאת שאין בה עומס. |
|
|
|
|
|
|
||
|
||||
|
מכיר 802.5? | |
|
|
|
|
|
||
|
||||
|
IEEE 802.5 ? לא. | |
|
|
|
|
|
||
|
||||
|
זה מזכיר קצת כיכר. |
|
|
|
|
|
|
||
|
||||
|
נכון. אני לא מכיר מספיק את הפרוטוקול כדי לדעת אם מחשב אחד יכול להשתלט על התעבורה (כאשר האסימון אצלו ויש לו הודעות להפיץ, הוא לא נותן צ'אנס לאחרים), אבל אני מניח שההתנהגות הטיפוסית יותר ידידותית מזו של נהגים שרוצים להגיע לעבודה בבוקר. ובכלל, נדמה לי ש token ring הולך ומאבד פופולריות לטובת ethernet שבעיותיו מתמעטות ברשתות מהירות עם מתג חכם (רמזור?). אולי לזה כיוונת. | |
|
|
|
|
|
||
|
||||
|
עכש''י האסימון מאפשר לבעליו לשלוח רק מספר מוגבל של הודעות. אגב, רמזור הוא לא יעיל בשל זמני האיתחול ( עד שהמכונית הראשונה יוצאת לדרך) והצורך לוודא שכל המכוניות בכיוון המאונך גמרו לגנוב את האדום לפני שהירוק מופיע. |
|
|
|
|
|
|
||
|
||||
|
הצורך לוודא שכל המכוניות בכיוון המאונך גמרו לגנוב את האדום לפני שהירוק מופיע הוא צורך מדומה, ולמעשה אינו קיים. החוק אוסר כניסה לצומת כאשר האור ברמזור שונה מירוק1, ומן הצד השני, גם כאשר האור ברמזור ירוק, החוק אוסר להיכנס לצומת אם אינו פנוי. הזמן המת המיועד כביכול לוודא שכל המכוניות בכיוון המאונך גמרו לגנוב את האדום לפני שהירוק מופיע הוא זה שיוצר את התופעה. __ 1 או, בתנאים מגבילים, צהוב מהבהב, אבל לא זה המקרה. |
|
|
|
|
|
|
||
|
||||
|
חוק? אני מבין שאדוני כותב מאירופה. | |
|
|
|
|
|
||
|
||||
|
מויקי הגעתי גם לאתר שמראה את ההקבלה למערכת פשוטה של קפיצים: http://www.davros.org/science/roadparadox.html תודה! |
|
|
|
|
|
|
||
|
||||
|
אני מציע לעצור כאן, לפני שמישהו יתהה אם הרעיונות האלה רלבנטיים גם לדילמות של שוק חפשי מול תכנון ריכוזי. | |
|
|
|
|
|
||
|
||||
|
חוששני שהשד כבר יצא מהבקבוק, הסוסים כבר ברחו מהאורווה, והחלב נשפך יחד עם התינוק. יזם זריז שבונה כביש בין הנקודות A ו-B עולה על כשל של היד הנעלמה. |
|
|
|
|
|
|
||
|
||||
|
"יזם זריז שבונה כביש בין הנקודות A ו-B עולה על כשל של היד הנעלמה". זה לא כל כך מתקבל על הדעת. הוא לא יודע מי העובדים שלו? הוא לא יודע של מי הידיים? |
|
|
|
|
|
|
||
|
||||
|
הידיים ויתר השלד הם של ספק-יהודים, לכן צריך לעצור את העבודות ולהעתיק את הקברים. | |
|
|
|
|
|
||
|
||||
|
הממם. אני מדמיין לעצמי אגודת סתרים של מהנדסי תחבורה חרדים-ליטאים האמונים על תורתו של Braess, הנפגשים בבתי מדרש בבני-ברק פעם בחצי שנה מול מפות כבישים מפורטות ומתכננים ביחד איך, בעזרת אתי-חפירה, כמה עצמות חמור, ובעיקר עוז-רוח, להציל את מדינת ישראל שוב-שוב מאסון תעבורתי מעשי ידיה-עצמה... | |
|
|
|
|
|
||
|
||||
|
או בקיצור, בראס-בנד. | |
|
|
|
|
|
||
|
||||
|
סרטון וידיאו באורך שעה: http://mitworld.mit.edu/video/812 | |
|
|
|
|
|
||
|
||||
|
לא ממש. שינית כאן קצת את ההגדרה של "מכונת טיורינג עוצרת", כי המשמעות המקורית היא "עוצרת עם פלט מתאים לגבי הבעיה", ואצלך המשמעות היא "עוצרת כנ"ל או לחלופין מושמדת/חדלה להתקיים". | |
|
|
|
|
|
||
|
||||
|
נראה לי שהכוונה הייתה שבעיית העצירה ''פתורה'' עבור תת המחלקה של מכונות הטיורינג שניתנות למימוש במציאות. | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
ההערה שלך נכונה למדי, אם כח להגנתי אטען שלא יהיה מי שיוכל לקבוע אם לא התקבל הפלט המצופה בננו-השניה שלפני הסוף. קלוש למדי, אני מודה. למען הדיוק, אני לא מדבר על מכונת טיורינג, לגביה אין לי ספקות מכל סוג, אלא על מימוש פיזי שלה. |
|
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |