תורת החישוביות/שקילות מודלי חישוב: הבדלים בין גרסאות בדף

 

=== שקילות מכונת טיורינג "חסרת מנוחה" למ"ט הסטנדרטית ===

 

על מנת להראות שקילות יש להוכיח שני כיוונים.

* כיוון ב' - סימלוץ מ"ט רגילה <math>M</math> על-ידי מכונה חסרת מנוחה <math>R</math>. הרעיון הוא כדלקמן: המכונה <math>R</math> תתנהג בדיוק כמו <math>M</math> פרט לכך שבכל פעם שהמכונה <math>M</math> תבצע מעבר בו הראש נשאר במקום, המכונה "חסרת המנוחה" <math>R</math> תזיז את הראש צעד ימינה ואז מייד צעד שמאלה חזרה ותמשיך בחישוב כמו <math>M</math>. באופן פורמלי, לכל מעבר <math>\delta(q,x)=(p,y,S)</math> ב-<math>M</math> נגדיר ב-<math>R</math> את המעבר: <math>\delta(q,x)=(p',y,R)</math> ואת המעברים <math>\delta(p',\sigma)=(p,\sigma,L)</math> לכל <math>\sigma\in\Gamma</math>. המעבר הראשון משנה את הסרט בהתאם להתנהגות M, ואז מזיז את הראש צעד אחד ימינה, כאשר הוא עובר למצב מיוחד <math>p'</math> שלמעשה "זוכר" שאנחנו צריכים לזוז ימינה ולעבור למצב <math>p</math> (כי במקור, M עברה למצב p). המעבר השני "מתעלם" ממה שרשום על הסרט, מזיז את הראש חזרה צעד שמאלה, ועובר למצב שזכרנו, p.