בתשובה לאיזי נבו, 04/03/08 17:47
מה חדש? 473188
אמנם תמוה, אבל ספציפית נראה שלגבי צ'רץ'-טורינג אתה טועה.
מתוך המאמר:
"מכאן, נראה שלטבע, הפועל על פי מכניקת הקוונטים, יש יתרון ביכולת החישוב שלו מול מחשב "קלאסי" (כלומר, מופרת תזת צ'רץ'-טיורינג הפיזיקלית בגירסתה החזקה)."
מתוך ויקיפדיה (http://en.wikipedia.org/wiki/Church%E2%80%93Turing_t...):
Another variation is the Strong Church–Turing Thesis (SCTT), which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory. It states (cf. Bernstein, Vazirani 1997):

"Any 'reasonable' model of computation can be efficiently simulated on a probabilistic Turing machine."
מה חדש? 473194
טוב, באמת לא זכרתי את ה-efficiently, ואם הכוונה במילה הזאת היא ל"בזמן ריצה שהוא לכל היותר חזקה קבועה של זמן הריצה המקורי", אז יש סיכוי טוב שהתזה האמורה באמת לא נכונה. מצד שני ב-‏1997 המחלקה BQP כבר היתה מוכרת ומוגדרת היטב, כך שלפרסם תזה כזאת נראה משונה. אני אשתדל לזכור לשאול את המנחה שלי בפגישתנו הקרובה.
מה חדש? 473195
הציטוט הוא ממאמר שפורסם ב-‏97, אין זה אומר שהתזה החזקה היא מ-‏97.

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

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