בתשובה לגדי אלכסנדרוביץ', 11/06/05 10:37
בקיצור 308005
איני מבין בכך דבר, אבל בהרצאה של האגודה הישראלית לפילוסופיה בחיפה, לפני כמה חודשים (אולי האירוע הכי פחות אמין לסוג כזה של מידע...) סופר על ידי ד"ר עמית הגר, מדען מחשב העוסק בתחום, שהמחשב הקוונטי אינו יכול לפתור בעיות שאינן כריעות ע"י מ"ט. את הפרטים לנימוקים שלו איני זוכר, וכנראה שמלכתחילה הם לא היו נהירים לי. איזושהי גרסה של תזת צ'רצ'-טיורינג הפיזיקלית הייתה קשורה לכך, ובאופן לא מפתיע עיקרון אי-הוודאות (ספציפית של הגדלים אנרגיה וזמן) גם כן. ניסיון נוסף לפשפש בזכרוני מעלה גם את שמו של וולפארם, אבל אני לא מצליח לחבר את כל פריטי המידע המפוקפקים האלה לידי טיעון שלם.

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

ההוכחה פשוט מראה שניתן לסמלץ כל מ"ט לא דטרמיניסטית N בעזרת מ"ט D דטרמיניסטית. מתיחסים אל החישוב של N על קלט w כאל עץ בו כל ענף מיצג את אחת האפשרויות במעברים הלא דטרמיניסטיים וכל צומת היא קונפיגורציה של המכונה. *הרעיון* מאחורי ההוכחה הוא שניתן ל-D לחפש לרוחב הענפים בעץ - אם היא מוצאת מצב מקבל היא תעצור ואם לא אז הסימולציה תמשך.

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

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

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