בתשובה לתוהה, 14/12/06 17:45
 |
|
 |
||
|
||||
 |
קראתי את הדיון לגבי הטענה שלך שההוכחה דבילית. לפי מה שהבנתי, אתה מקבל את תקפות ההוכחה, אבל מפקפק במשמעות המעשית שלה. הרבה פעמים, משפט נראה מאוד עמוק, אבל ההוכחה שלו מסתמכת על טיעונים מאוד בסיסיים, וכמעט מובנים מאליהם. זה בדיוק הכוח של ההוכחות. לכן כשמסתכלים על תהליך ההוכחה, קשה לפעמים להאמין שבאמת הראנו משהו עמוק, כי כל צעד שעשינו בדרך לא היה ממש עמוק. אם ההוכחה מאכזבת אותך, אני מציע לך לשים אותה בצד. מרגע שהמשפט הוכח, אפשר לבחון את המשפט כשלעצמו, ולשכוח איך הוא הוכח. המשפט עצמו טוען שלא קיים אלגוריתם שפותר את בעיית העצירה. בוא נניח לרגע שבאמת הבעיה היא רק במקרה פרטי אחד, כפי שאתה טוען, שבו המכונה מקבלת ככקלט את הקידוד של עצמה. אילו באמת היה מדובר במקרה פרטי אחד שבו אנחנו גם יודעים אם המכונה תעצור, אז היה אפשר לפתור את הבעיה בקלות, היינו בונים מכונה שפותרת את כל שאר המקרים, ומקרה הנ"ל מורים לה לטפל בנפרד. לכן ברור שהבעיה היא לא עם במקרה פרטי אחד, או במספר סופי של מקרים. ובכלל, לכל אלגוריתם יש אינסוף קידודים אפשריים. איך תדע לקבוע שהמכונה קיבלה קידוד של האלגוריתם של עצמה? גם זאת בעיה שאין לה אלגוריתם. אני מציע לך לחשוב שוב אם אתה יכול להוכיח שהקומפיילר לא יכול לדעת באיזה משתנים התוכנית תשתמש ובאיזה לא. אם אתה יכול להוכיח זאת, אז באמת הטענה נכונה במובן הכי מעשי שיש (וזה אכן המצב למיטב זכרוני). ואם הקומפילר כן יכול לפתור את הבעיה הזאת, אז לא תוכל להוכיח שהוא לא יכול, בעזרת תעלולים לוגיים כדוגמת הפנייה עצמית. כלומר אם יש אלגוריתם שפותר את הבעיה, אז לא תהיה לו בעיה לדעת באיזה משתנים הוא עצמו משתמשו באיזה לא. לגבי המאמר הבא - מה שלא הבנתי בקשר לעניין הסיבוכיות, זה האם היא תלויה במודל החישובי שבו משתמשים. כלומר, האם ייתכן שנוכיח שבעיה מסויימת היא בעלת סיבוכיות לא פולינומית על מכונת טיורינג, אבל ייתכן שימצא מודל חישוב בעתיד, ששקול חישובית למכונת טיורניג, שבו אפשר לפתור את הבעיה בזמן פולינומי. אם באופן תאורטי זה אפשרי, אז זה קצת בעיה לא? |
 |
 |
 |
|
|
|
||
|
||||
|
בקשר לסיבוכיות - אני בהחלט אנסה להתייחס לזה במאמר הבא. בעיקרון, הסיבוכיות מאוד תלויה במודל שבו משתמשים. אחת הסיבות שבגללן משתמשים בסיבוכיות פולינומית כדי לציין סיבוכיות "טובה" היא שההגדרה הזו מבטיחה תלות נמוכה למדי במודל - אלגוריתם שהוא פולינומי במכונת טיורינג "פושטית" יהיה פולינומי (עם פולינום אחר) גם במכונת טיורינג עם מאה סרטים, וכו'. אלא שיש מקומות שבהם שינוי המודל כבר גורר כמעט בהכרח שינוי בסיבוכיות. הבעיה של P=NP היא בדיוק דוגמה לכך - אם אנחנו מוסיפים למכונה אי דטרמיניזם, כבר לא ברור לנו האם בעיה שהיא פולינומית במכונה האי דטרמיניסטית היא בהכרח גם פולינומית במכונה הדטרמיניסטית (וזאת להבדיל משאלת הכריעות - מכונת טיורינג דטרמיניסטית שקולה לאי דטרמיניסטית בכל הנוגע לשאלה האם ניתן להכריע בעיה מסויימת או לא). עוד דוגמה: יש קישור למאמר של איזי למעלה. במאמר הזה מתוארים "אלגוריתמים קוונטים". אני לא מתמצא בתחום הזה, אבל למיטב הבנתי גם במקרה הזה מדובר על מודל חזק יותר של מכונת טיורינג, שיכול לפתור בעיות מסויימות (כמו פירוק לגורמים) הרבה יותר מהר ממכונה רגילה. החשיבות של האלגוריתמים הללו היא שבניגוד למכונה אי דטרמיניסטית, חושבים שניתן יהיה לממש מכונה קוואנטית שמריצה אותם בפועל. בקיצור, סיבוכיות הוא תחום מסובך, ואני לא מכיר אפילו את קצה הקרחון שלו. |
|
|
|
|
|
|
||
|
||||
|
אגב, סקוט ארונסון מציע השערה שקצת מזכירה את תיזת שכ"ג-עמית: The NP Hardness Assumption: There is no physical means to solve NP-complete problems in polynomial time. לשאר ההרצאה המשעשעת: |
|
|
|
|
|
|
||
|
||||
|
מה זה ה-NP הזה, במטותא? | |
|
|
|
|
|
||
|
||||
|
עכש"י זה קבוצת כל השאלות (החישוביות) שאפשר לוודא(או לפסול?) פיתרון משוער שלהן בזמן חישוב פולינומיאלי ( כלומר חזקה של אורך השאלה) | |
|
|
|
|
|
||
|
||||
|
תודה. נניח שהבנתי:). אבל אם כך, מה זה P=NP? | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
מאמר נחמד מאוד! (אפשר לשאול מהי תיזת שכ"ג-עמית? יש לי קשר לזה?) |
|
|
|
|
|
|
||
|
||||
|
תיזת שכ"ג עמית: אין דרך פיסיקלית להבחין בין החלטה חופשית להחלטה אקראית. תגובה 423933 |
|
|
|
|
|
|
||
|
||||
|
ואללה? אני בקושי זוכר ששוחחתי עם שכ"ג על העניין הזה, אך בכל אופן אני מסכים עם עצמי-מלפני-כמה-זמן-בשיחה-עם-שכ"ג: ודאי שאין דרך *אמפירית* להבחין (אצל מישהו אחר) בין החלטה "חופשית" להחלטה מוכתבת אלגוריתמית עם מרכיבים אקראיים. הייתי בטוח שזה, לפחות, מוסכם על כולם (אפילו על המתווכחים ומתווכחות עם שכ"ג בלהט). | |
|
|
|
|
|
||
|
||||
|
אליבא דדב אנשלוביץ והמקור בר-הסמכא שלו זה בכלל לא מוסכם (אלא אם כן אני לא מבין מה הוא אומר). (לא שוחחת. כתבת מכתב, בסמוך לפרסום המאמר שלי, ובו אמרת משהו ברוח הזאת) |
|
|
|
|
|
|
||
|
||||
|
חשבתי שהמקור בר-הסמכא הוכיח שאי-שוויון בל מוכיח שיש בחירה חופשית או משהו כזה. זה נותן גם מבחן אמפירי? (כן, לזה התכוונתי. אני מרבה לשוחח בתקתוק). |
|
|
|
|
|
|
||
|
||||
|
טענת המקור של דב היא הרבה יותר צנועה, ולא *לחלוטין* נטולת בסיס: שללא הנחת בחירה חופשית, אי אפשר להסיק את המסקנות הידועות מניסוי בל. | |
|
|
|
|
|
||
|
||||
|
תגובה 229301 | |
|
|
|
|
|
||
|
||||
|
צודק: תיזת שכ"ג עמית מיסודו של איזי. | |
|
|
|
|
|
||
|
||||
|
אני מתנצל. כל השיחה ההיא נשכחה ממני. | |
|
|
|
|
|
||
|
||||
|
אלא אם כן הן אותו הדבר (תגובה 56073 מדהים כמה האייל נשאר במקום)... | |
|
|
|
|
|
||
|
||||
|
רק להבהיר, לא ידועה כיום אף בעיה ב NP-Complete שיש לה אלגוריתם פולינומיאלי במודל של חישוב קוואנטי. בפרט, אין הוכחה שמודל החישוב הקוונטי חזק יותר ממכונת טיורינג קלאסית. | |
|
|
|
|
|
||
|
||||
|
כמובן. תודה על התיקון. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |