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