בתשובה לגדי אלכסנדרוביץ', 04/01/07 8:51
 |
|
 |
||
|
||||
 |
אני מוכן להניח שיש בעולם לוחות שחמט, אבל לגמרי לא בטוח שיש בו משוואות מהמעלה החמישית. איפה הן גרות? (היום הוא יום אי-זוגי, ולכן אינני פלטוניסט) "תבדוק את הטענה עבור מימושים שלו בעולם האמיתי" הוא לוז העניין. לכולנו יש מימוש יומיומי שאנחחו מכירים היטב ולגביו בעיית הריצוף פתורה. האם ייתכנו מימושים אחרים? הטענה שלי היא שאולי כן. לא "אולי" במשמעות שהייתי מוכן לשים על זה כסף, אלא "אולי" שפירושו "לא ממש בלתי אפשרי". |
 |
 |
 |
|
|
|
||
|
||||
|
אני לא צריך שהמשוואות יגורו בשום מקום. אני צריך שתביא לי נוסחה עבורן, ולא אכפת לי איפה היא גרה. השאלה היא האם העובדה שאתה בן אדם שחי בעולם האמיתי ואת הנוסחאות שלך אתה כותב על נייר (שיכול להיות גם טבעת מביוס) ובעיפרון עוזר לך במשהו. דווקא כאן הקשר לנושא המאמר מורגש יותר טוב. מכונת טיורינג היא מודל מופשט של מחשב; כל מחשב בימינו הוא מימוש פיזי כלשהו של מכונת טיורינג (שבשל אילוצים טכניים הוא אפילו יותר מוגבל מאשר מכונת טיורינג), ממש כמו שהנוסחאות שאתה כותב על נייר ועיפרון הן ייצוג פיזי של רעיון מתמטי. אם אפילו הרעיון המתמטי ה"אידאלי" לא בר-ביצוע, על אחת כמה וכמה המימושים הפיזיים לא יהיו מסוגלים לבצע זאת. (ושוב, השאלה "האם יש מימושים אחרים" מפספסת את הנקודה - מימוש ש*לא* מקיים את התכונות שעוזי הציע הוא תשובה טובה לבעיה אחרת - הוא *אינו* מימוש של לוח שחמט). |
|
|
|
|
|
|
||
|
||||
|
המשוואות שאתה מדבר עליהן הן יצורים מתמטיים, או לפחות כך אני תופס זאת. מה שכתוב על נייר הם כל מיני סימנים משונים, שאין שום טעם לשאול אם יש להם שורש: הם לא צמחים ולא שיניים. | |
|
|
|
|
|
||
|
||||
|
השאלה היא לא שאלה של "האם קיים שורש" (תמיד קיים) אלא של "האם קיימת נוסחה שמופיעות בה רק הפעולות האלו והאלו". כלומר, מה שנבדק הוא במפורש יכולת הביטוי הפיזית שלנו. אבל אם זה מפריע לך, באמת שקיימות אלפי דוגמאות אחרות. בוא נניח שאני נותן לך טקסט שהוצפן בעזרת פנקס חד פעמי ושואל אותך האם יש לך דרך כלשהי (חוץ מניחוש) לגלות מהו הטקסט. האם זה שאני נותן לך את הטקסט פיזית ואנחנו בעולם פיזיקלי יעזור לך לפענח אותו? האם הטקסט הוא "יצור מתמטי" ומה שכתוב על הנייר הוא "כל מני סימנים משונים"? ונניח שכן, אז מה? עדיין, האתגר של להמיר את הסימנים המשונים הללו לאוסף סימנים משונים אחר ששמור אצלי בכספת הוא אתגר פיזי שאתה לא מסוגל לבצע. |
|
|
|
|
|
|
||
|
||||
|
אשר לרישא: אתה כמובן צודק והניסוח שלי היה מטופש (אבל אם אנחנו כבר כאן, יש מבחן פשוט שקובע אם יש שורש ממשי?). הדוגמא עם פענוח טקסטואלי מעניינת, אבל בעולם האמיתי אני אוכל לבצע את המטלה בקלות יחסית בעזרת רתכת. עכשיו בטח תטען שאם הפירוש נמצא אצלך במוח ולא בכספת לא אוכל לעמוד במשימה. לא יודע. אולי לשב"כ יש, או יהיה, fMRI שמתגבר גם על המכשול הזה. (אני לא יודע בעצמי באיזו מידה אני רציני. נראה לאן הדיון הזה יוביל) |
|
|
|
|
|
|
||
|
||||
|
בקיצור, בכל פעם שאני מציג לך בעיה, עם "כללי משחק" מוגדרים, אתה אומר שהיא פתירה על ידי זה שמתעלמים מכללי המשחק. בדוגמה הנוכחית אולי אפשר בכל זאת ללכוד אותך: המקור של הטקסט לא נמצא בשום מקום (הוא הושלך ללוע הר האבדון). עכשיו לך תפענח את הטקסט ותוודא שהפיענוח שלך אכן נכון. (אני משער שהצעד הבא יהיה לטעון שתמיד קיימת הסתברות לגלות את הטקסט על ידי ניחוש, פשוט אי אפשר לוודא שהניחוש נכון). (אם הפולינום הוא במקדמים ממשיים וממעלה אי זוגית, תמיד יש לו שורש ממשי. מעבר לכך אני לא יודע - תצטרך לחכות למתמטיקאים). |
|
|
|
|
|
|
||
|
||||
|
לא, אני אומר ש"כללי המשחק" משאירים פתח לספקנות מסויימת. כתבתי כאן הודעה די ארוכה, אבל בסיומה הגעתי למסקנה שאני לא באמת רוצה להגן על העמדה הזאת. נראה, אני צריך לחשוב על זה עוד קצת1. ____________ 1- בד"כ זה אומר שאף פעם לא אחזור לזה. |
|
|
|
|
|
|
||
|
||||
|
אם אתה מעוניין בספקנות בלבד, בבקשה; כמו שאמרתי קודם, תמיד אפשר לומר "מה אם" על הכל. שנזכיר כאן שהמתמטיקאים עובדים עם מערכת אקסיומות שלא יכולה להוכיח שאין בה סתירה? הבעיה מתחילה כשהגישה של "אי אפשר להוכיח שום דבר" גורמת לאנשים לחשוב "היי, הבעיה בבעיית העצירה היא בסך הכל שהחבר'ה האלו עובדים עם מודל מיושן כמו מכונת טיורינג! אני *בטוח* שעל הפנטיום החדש שלי אפשר לפתור אותה, אז אני אבזבז חודש בלכתוב תוכנה שעושה את זה!". (מצד שלישי, לרוב האנשים שיאמרו כזה דבר הם בדיוק מהסוג שהיית רוצה שיעזוב אותך במנוחה למשך חודש). |
|
|
|
|
|
|
||
|
||||
|
אני ממש לא נמנה עם האוחזים בדעה שכל ההשערות שקולות כי לא ניתן להוכיח אף אחת מהן. להיפך, הגישה הזאת מעלה אצלי את הסעיף פעם אחר פעם. בעולם האמיתי בעית העצירה פתורה, כמובן: כל מימוש פיזיקלי של מכונת טיורינג עוצר בסופו של דבר, גם אם "סופו של דבר" הוא בעוד כמה מיליארד שנים, כשכל היקום יהיה בשיווי משקל תרמודינמי בסביבות האפס המוחלט. |
|
|
|
|
|
|
||
|
||||
|
נכון, אבל בדיבורים כמו ''בעולם האמיתי בעיית העצירה פתורה'' לוקה באותה בעייתיות שאפיינה את הדיון המוקדם יותר שלי עם זה שלא הבין מה השוס הגדול כאן. אולי בעיית העצירה לכשעצמה אינה בעלת עניין מעשי בעולם שלנו, אבל אפשר להוכיח בעזרתה אי כריעות של בעיות שיישארו לא כריעות גם בעולם שלנו, דוגמת בעיית מציאת דרך כללית לפתרון משוואה דיופנטית. | |
|
|
|
|
|
||
|
||||
|
כמובן. אני בהחלט איתך בקשר לעניין העיקרי, כל עוד אנחנו זוכרים ש"משוואה דיופנטית" היא יצור מתמטי, לא פיזיקלי (גם ביום שישי). הדוגמא היפה שקהלת הביא בקשר לפתרון "משוואות" בעזרת מערכת קפיצים ומשקולות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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |