מי אמר שהאלים לא משחקים בקוביות?

בתשובה לעומר, 11/06/05 18:20

בקיצור

308152

אביב י. • בתשובה לעומר

יום א', 12/6/2005, 10:29

הטענה: לכל מ"ט לא דטרמיניסטית יש מ"ט דטרמניסטית השקולה לה.

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

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

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

המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
RSS מאמרים \| כתבו למערכת \| אודות האתר \| טרם התעדכנת \| ארכיון \| חיפוש \| עזרה \| תנאי שימוש והצהרת נגישות	© כל הזכויות שמורות