בתשובה לתוהה, 14/12/06 17:45
ההוכחה הזאת פשוט דבילית 426169
קראתי את הדיון לגבי הטענה שלך שההוכחה דבילית. לפי מה שהבנתי, אתה מקבל את תקפות ההוכחה, אבל מפקפק במשמעות המעשית שלה.
הרבה פעמים, משפט נראה מאוד עמוק, אבל ההוכחה שלו מסתמכת על טיעונים מאוד בסיסיים, וכמעט מובנים מאליהם. זה בדיוק הכוח של ההוכחות. לכן כשמסתכלים על תהליך ההוכחה, קשה לפעמים להאמין שבאמת הראנו משהו עמוק, כי כל צעד שעשינו בדרך לא היה ממש עמוק.
אם ההוכחה מאכזבת אותך, אני מציע לך לשים אותה בצד. מרגע שהמשפט הוכח, אפשר לבחון את המשפט כשלעצמו, ולשכוח איך הוא הוכח.
המשפט עצמו טוען שלא קיים אלגוריתם שפותר את בעיית העצירה. בוא נניח לרגע שבאמת הבעיה היא רק במקרה פרטי אחד, כפי שאתה טוען, שבו המכונה מקבלת ככקלט את הקידוד של עצמה. אילו באמת היה מדובר במקרה פרטי אחד שבו אנחנו גם יודעים אם המכונה תעצור, אז היה אפשר לפתור את הבעיה בקלות, היינו בונים מכונה שפותרת את כל שאר המקרים, ומקרה הנ"ל מורים לה לטפל בנפרד. לכן ברור שהבעיה היא לא עם במקרה פרטי אחד, או במספר סופי של מקרים. ובכלל, לכל אלגוריתם יש אינסוף קידודים אפשריים. איך תדע לקבוע שהמכונה קיבלה קידוד של האלגוריתם של עצמה? גם זאת בעיה שאין לה אלגוריתם.
אני מציע לך לחשוב שוב אם אתה יכול להוכיח שהקומפיילר לא יכול לדעת באיזה משתנים התוכנית תשתמש ובאיזה לא. אם אתה יכול להוכיח זאת, אז באמת הטענה נכונה במובן הכי מעשי שיש (וזה אכן המצב למיטב זכרוני). ואם הקומפילר כן יכול לפתור את הבעיה הזאת, אז לא תוכל להוכיח שהוא לא יכול, בעזרת תעלולים לוגיים כדוגמת הפנייה עצמית. כלומר אם יש אלגוריתם שפותר את הבעיה, אז לא תהיה לו בעיה לדעת באיזה משתנים הוא עצמו משתמשו באיזה לא.
לגבי המאמר הבא - מה שלא הבנתי בקשר לעניין הסיבוכיות, זה האם היא תלויה במודל החישובי שבו משתמשים. כלומר, האם ייתכן שנוכיח שבעיה מסויימת היא בעלת סיבוכיות לא פולינומית על מכונת טיורינג, אבל ייתכן שימצא מודל חישוב בעתיד, ששקול חישובית למכונת טיורניג, שבו אפשר לפתור את הבעיה בזמן פולינומי. אם באופן תאורטי זה אפשרי, אז זה קצת בעיה לא?
ההוכחה הזאת פשוט דבילית 426182
בקשר לסיבוכיות - אני בהחלט אנסה להתייחס לזה במאמר הבא. בעיקרון, הסיבוכיות מאוד תלויה במודל שבו משתמשים. אחת הסיבות שבגללן משתמשים בסיבוכיות פולינומית כדי לציין סיבוכיות "טובה" היא שההגדרה הזו מבטיחה תלות נמוכה למדי במודל - אלגוריתם שהוא פולינומי במכונת טיורינג "פושטית" יהיה פולינומי (עם פולינום אחר) גם במכונת טיורינג עם מאה סרטים, וכו'.

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

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

בקיצור, סיבוכיות הוא תחום מסובך, ואני לא מכיר אפילו את קצה הקרחון שלו.
ההוכחה הזאת פשוט דבילית 426188
אגב, סקוט ארונסון מציע השערה שקצת מזכירה את תיזת שכ"ג-עמית:
The NP Hardness Assumption: There is no physical means to solve NP-complete problems in polynomial time.

לשאר ההרצאה המשעשעת:
ההוכחה הזאת פשוט דבילית 426211
מה זה ה-NP הזה, במטותא?
ההוכחה הזאת פשוט דבילית 426218
עכש"י זה קבוצת כל השאלות (החישוביות) שאפשר לוודא(או לפסול?) פיתרון משוער שלהן בזמן חישוב פולינומיאלי ( כלומר חזקה של אורך השאלה)
ההוכחה הזאת פשוט דבילית 426222
תודה. נניח שהבנתי:). אבל אם כך, מה זה P=NP?
ההוכחה הזאת פשוט דבילית 426225
ההוכחה הזאת פשוט דבילית 426216
מאמר נחמד מאוד!

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

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

(כן, לזה התכוונתי. אני מרבה לשוחח בתקתוק).
ההוכחה הזאת פשוט דבילית 426689
טענת המקור של דב היא הרבה יותר צנועה, ולא *לחלוטין* נטולת בסיס: שללא הנחת בחירה חופשית, אי אפשר להסיק את המסקנות הידועות מניסוי בל.
איזו חוצפה! 426487
תגובה 229301
איזו חוצפה! 426488
צודק: תיזת שכ"ג עמית מיסודו של איזי.
איזו חוצפה! 426539
אני מתנצל. כל השיחה ההיא נשכחה ממני.
ההוכחה הזאת פשוט דבילית 426638
אלא אם כן הן אותו הדבר (תגובה 56073 מדהים כמה האייל נשאר במקום)...
ההוכחה הזאת פשוט דבילית 426485
רק להבהיר, לא ידועה כיום אף בעיה ב NP-Complete שיש לה אלגוריתם פולינומיאלי במודל של חישוב קוואנטי. בפרט, אין הוכחה שמודל החישוב הקוונטי חזק יותר ממכונת טיורינג קלאסית.
ההוכחה הזאת פשוט דבילית 426495
כמובן. תודה על התיקון.

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

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