בתשובה לגדי אלכסנדרוביץ', 23/05/07 21:05
 |
|
 |
||
|
||||
 |
"שבבי מחשב וזרמים חשמליים" הם בסך הכל הדרך הפיזית שבחרת לפתור את הבעיה. הבעיה היא מתמטית ובסופו של דבר אתה יכול להגיע לאותו הפתרון עם נייר ועט. מכונת טיורינג או לא מכונת טיורינג? |  |
 |
 |
|
|
|
||
|
||||
|
שוב, השאלה היא מה זה "הבעיה היא מתמטית". אם מודדים זמני ריצה, אז יש חשיבות לדרך המימוש הפיזית. אם מתעניינים בשאלה "כמה התוצאות שהאלגוריתם מחזיר מדוייקות" אז אכן אין חשיבות לשאלה "איך בחרנו לממש", אבל אז אפשר לחשוב על אמצעי המימוש כעל "כלי הניסוי" - והניסוי הוא עדיין אמפירי. אנסה להדגים את זה עם קריפטוגרפיה: נניח שהמצאת אלגוריתם קסום שאמור לפענח כל כתב סתר שהוצפן בשיטה מסויימת. ניסוי אמפירי להפרכת הטענה הזו מתבסס על כך שיריב ערמומי יתן לך אוסף של כתבי סתר שהוצפנו במטרה לעבוד על האלגוריתם. השאלה מי יפעיל את האלגוריתם כדי לפצח את כתבי הסתר - אתה עם נייר ועפרון או מחשב - היא טכנית, אבל השאלה הסופית שאותה בוחנים תזכה רק לתשובה אמפירית (כי לא נוכל לבדוק את האלגוריתם על כל כתבי הסתר הקיימים, ואין לנו הוכחה מתמטית לטענה שהוא עובד תמיד). |
|
|
|
|
|
|
||
|
||||
|
אבל למיטב ידיעתי, כאשר מודדים זמני ריצה, מה שחשוב זה אופן מימוש התוכנה, לא? אחרת הבעיה כבר קשורה להנדסת חשמל, ולא למדעי המחשב. כי על קריי ועל מחשב XT אותו פתרון ירוץ בזמנים שונים, ואנחנו רוצים להכריע בין _פתרונות_, לא בין חומרות. או שאני טועה כאן לחלוטין? אם אני לא טועה, את קריטריון זמן הריצה ניתן לתרגם לקריטריון "מספר צעדים" לפתרון והם שקולים. קריטריון "מספר צעדים" הוא זהה ולא תלוי במכונת הטיורינג הספציפית שעושה אותו - בין אם מדובר באדם או בקומודור 64. ושוב - זו בעיה מתמטית, ולא "אמפירית". כל זאת בהנחה שאני צודק. לא הבנתי לחלוטין את הדוגמה עם הקריפטוגרפיה. גם כאן מדובר בבעיה _מתמטית_, לא? אבל מכיוון שלא הבנתי עדיף שתסביר, אם אתה מוכן. באסה שליברפול הפסידו. אין צדק. |
|
|
|
|
|
|
||
|
||||
|
זה לא בהכרח נכון, כי מספר הצעדים כן תלוי במעבד - יש מעבדים שמממשים בתור פרימיטיבים פקודות שבמעבדים אחרים היו לוקחות כמה פקודות מכונה, וכדאי גם לזכור שבימינו יש מחשבים עם מספר מעבדים שרצים בו זמנית. לכן לשאלות של זמן ריצה יכול להיות עניין - לא עניין תיאורטי, חס ושלום, אבל עניין. כדאי לשים לב שלא מדובר כאן על הבדלים מסדרי הגודל שבהם עוסקת תורת הסיבוכיות (למשל, ההבדל בין P ו-NP), אבל זו אכן אחת הסיבות שבגללה תורת הסיבוכיות מגדירה "חישוב יעיל" בתור P למרות מהומת האלוהים שיש בפנים - זה מבטיח לנו אי תלות גדולה יחסית במודל. ובכל זאת, מתחת לכסות ה"תיאורטית" הזו רוחשים חיים "אמפיריים". הנה דוגמה למשהו שתורת הסיבוכיות בכלל לא רלוונטית אליו: בעיית השחמט. יש משפט של צרמלו שאומר שכל משחק דמוי-שחמט (לא ניכנס למה זה - העיקר ששחמט הוא כזה) מקיים אחת משלוש אפשרויות: או שללבן יש דרך להבטיח ניצחון בכל משחק, בלי תלות במה עושה השחור; או שלשחור יש דרך כזו, או שלכל אחד מהשחקנים יש דרך להבטיח תיקו. אם נדע ולו על אחת מהדרכים הללו, המשחק יאבד הרבה מהטעם שבו, ובפרט אם נגלה שללבן, למשל, יש דרך להבטיח תמיד ניצחון. באופן תיאורטי, לא קשה לבדוק את זה - פשוט עוברים על "עץ המשחק" (תיאור כל הצעדים האפשריים במשחק) וסורקים אותו עד סופו. מכיוון שגודל עץ המשחק הוא מספר קבוע, ואילו תורת הסיבוכיות מתעניינת בקצב גדילה, הבעייה "לא מעניינת" מבחינתה - אבל זו הרי בכל זאת בעיה מעניינת, והתשובה לה תלוייה בגורמים "מעשיים" בלבד - המימוש היעיל של החיפוש, ואולי גם היוריסטיקות שיסייעו במציאת הפתרון וצמצום מרחב החיפוש. באשר לקריפטוגרפיה - ייתכן מאוד שאתה צודק וזו בעיה "מתמטית", אבל לא ברורה לי ההפרדה החדה שעושים בינה ובין בעיה פיזיקלית, מבחינת ה"אמפיריות" של הפתרונות. |
|
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |