בתשובה לאלון עמית, 11/06/05 4:07
 |
|
 |
||
|
||||
 |
אגב, מה עם חישוב קוואנטי? יש מודל של מכונת טיורינג שמשתמש בחישוב קוואנטי, והכוח החישובי שלו גדול יותר משל מכונת טיורינג "רגילה" (היא אי דטרמיניסטית על פי הגדרה, לא? או שזה רק אוטומט מחסנית?), או שהשיפור הוא רק במונחי סיבוכיות, לא כריעות? |  |
 |
 |
|
|
|
||
|
||||
|
איני מבין בכך דבר, אבל בהרצאה של האגודה הישראלית לפילוסופיה בחיפה, לפני כמה חודשים (אולי האירוע הכי פחות אמין לסוג כזה של מידע...) סופר על ידי ד"ר עמית הגר, מדען מחשב העוסק בתחום, שהמחשב הקוונטי אינו יכול לפתור בעיות שאינן כריעות ע"י מ"ט. את הפרטים לנימוקים שלו איני זוכר, וכנראה שמלכתחילה הם לא היו נהירים לי. איזושהי גרסה של תזת צ'רצ'-טיורינג הפיזיקלית הייתה קשורה לכך, ובאופן לא מפתיע עיקרון אי-הוודאות (ספציפית של הגדלים אנרגיה וזמן) גם כן. ניסיון נוסף לפשפש בזכרוני מעלה גם את שמו של וולפארם, אבל אני לא מצליח לחבר את כל פריטי המידע המפוקפקים האלה לידי טיעון שלם. אם למישהו יש מושג על מה אני מדבר, אשמח לשמוע :) |
|
|
|
|
|
|
||
|
||||
|
הטענה: לכל מ"ט לא דטרמיניסטית יש מ"ט דטרמניסטית השקולה לה. ההוכחה פשוט מראה שניתן לסמלץ כל מ"ט לא דטרמיניסטית N בעזרת מ"ט D דטרמיניסטית. מתיחסים אל החישוב של N על קלט w כאל עץ בו כל ענף מיצג את אחת האפשרויות במעברים הלא דטרמיניסטיים וכל צומת היא קונפיגורציה של המכונה. *הרעיון* מאחורי ההוכחה הוא שניתן ל-D לחפש לרוחב הענפים בעץ - אם היא מוצאת מצב מקבל היא תעצור ואם לא אז הסימולציה תמשך. הסימולציה הדטרמניסטית של המכונה הלא דטרמניסטית אולי תקח הרבה יותר "זמן", אבל זה כבר סיפור אחר. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |