Question

model

מודל מ"ט בגיל העמידה לחישוב פונקציות הוא מודל זהה למודל הסטנדרטי של מ"ט לחישוב פונקציות פרט לשינויים הבאים:

  • למכונה אין מצבים סופיים, ולכן המכונה לעולם לא עוצרת.
  • נגיד שמכונה נעמדת בצעד החישוב ה tt אם מצעד חישוב זה והלאה המכונה מבצעת אך ורק תזוזות Stay ולעולם לא תבצע יותר תזוזות Left או Right
  • עבור קלט xx פלט המכונה הוא המילה yy שנמצאת משמאל לראש כאשר המכונה נעמדת.

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

1

Answers

נראה שמודל זה שקול למודל מכונת טיורינג.

בהינתן מ"ט במודל הסטנדרטי נבנה מ"ט במודל גיל העמידה כך שלכל xx פלטי המכונות זהים. את הבניה נבצע על ידי כך שנחליף כל מצב מקבל של המ"ט הסטנדרטית במצב שגורם למ"ט לעמוד, כלומר פונקציית המעברים במצב זה תמיד מבצעת תזוזת Stay ללא קשר לתו הנקרא.

מצד שני בהינתן מ"ט בגיל העמידה נבנה מ"ט סטנדרטית באופן הבא: המ"ט תריץ את מ"ט גיל העמידה וברגע שהיא תזהה עמידה היא תעבור למצב מקבל. נשים לב שניתן לזהות עמידה אם התבצעו QΣ|Q||\Sigma| תזוזות Stay ברצף.

1
Feedback