בתשובה לאלון עמית, 23/02/04 20:52
 |
|
 |
||
|
||||
 |
לגבי מודלי חישוב שאינם ניתנים לרדוקציה למכונת טיורינג רגילה, קיימים כמובן חישובים הסתברותיים, הניתנים לחישוב ע"י מכונת טיורינג הסתברותית (אם אתה במצב מספר 67 וקורא 1 תעבור למצב 112 בהסתברות 43 או למצב 86 בהסתברות 57. אם אתה קורא 0 תעבור למצב 98 בהסתברות 33 ולמצב 65 בהסתברות 67) וכן אלגוריתמים קוונטיים הניתנים לחישוב ע"י מכונת טיורינג קוונטית. (דטרמיניסטית או הסתברותית) אפשר כמובן לטעון שאלגוריתם הסתברותי או קוונטי הוא לא אלגוריתם אלא משהו אחר, אבל זה כבר עניין של הגדרה. |
 |
 |
 |
|
|
|
||
|
||||
|
נכון, אבל זהירות - העניין באלגוריתמים הסתברותיים וקוונטיים נובע מיכולתם לחשב *ביעילות* בעיות קשות, לא (ככל הידוע לי) לפתור בעיות ש*אינן ניתנות לחישוב*. אם יש אלגוריתם הסתברותי המסוגל לבדוק אם גרף הוא 3-צביע (נניח), אז ודאי שיש גם אלגוריתם דטרמיניסטי המסוגל לעשות זאת, רק הרבה יותר לאט. ההישג העיקרי של המודלים הקוונטיים של חישוב הוא בפירוק *יעיל* של מספרים, שהיא כמובן בעייה טריויאלית מההיבט החישובי. אם מדובר על חישוביות, ולא סיבוכיות, אז חישוב הסתברותי איננו מעשיר את הרפרטואר, ואני סבור שגם קוונטי לא (ייתכן שאני טועה בנקודה זו, עבר זמן מאז התעניינתי בתחום). | |
|
|
|
|
|
||
|
||||
|
אתה לא טועה (מחשבים קוונטיים ניתנים לסימולציה ע''י מכונות טיורינג - הבעיה היא שהסימולציה איטית). | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שאתה צודק. עד כמה שאני זוכר, מכונת טיורינג לא יכולה לסמלץ במדוייק מכונת טיורינג קוונטית שנמצאת בסופרפוזיציה של כמה מצבים. ניתן לייצג קרוב בלבד. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שאתה מתכוון לומר שאם למכונה הקוונטית מותר להיות בסופרפוזיציה של כמה מצבים עם משקל ממשי לכל מצב, אז לא ניתן לסמלץ זאת בדיוק ע''י מכונה דטרמיניסטית שיש לה אפילו יותר מצבים, אחד לכל קומבינציה של מצבים קוונטיים, כי דרושים אינסוף מצבים לסימלוץ. אבל אני לא בטוח שזה משנה לשאלת ה''מה ניתן לחשב''. אם נכון לחשוב על מכונה קוונטית בסופרפוזיציה כנמצאת במספר מצבים, כל אחד עם משקל (אפילו ממשי), וכשהיא מתקדמת היא מגיעה לסופרפוזיציה של מצבים אחרים עם משקלות אבל באופן שכל מצב חדש (עם משקל חיובי) הוא נגיש ממצב ישן (עם משקל חיובי), אז לכל חישוב שלה יש חישוב חוקי של המכונה הקלאסית המתאימה ש''במקרה'' בוחר נכון בכל שלב לאן ללכת. שוב, השאלה היא רק אם החישוב הקלאסי הוא ''מסלול'' בגרף המסובך של החישוב הקוונטי, ואם יש איזושהי דרך לצאת מהמצב ההתחלתי (או אחד מהם, אם יש כמה) ולהגיע לתוצאה הסופית המבוקשת. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |