2.2.1. תרגיל
הוכח כי לכל מ"ט קיימת מ"ט המחשבת את אותה פונקציה, אשר אינה מנסה ליפול מהסרט
(על ידי נסיון ללכת שמאלה כאשר הראש נמצא בתא השמאלי ביותר בסרט).
פתרון:
נגדים בניה של מכונה אשר לא מנסה ליפול
מהסרט:
נגדיר בצורה הבאה: שעבור כל אות ב-
או ב- נגדיר אות מקבילה .
האלגוריתם:
אתחול: המכונה
תחליף את האות הראשונה
באות המקבילה .
ריצה:
במהלך החישוב, בכל פעם שהמכונה נתקלת באות השייכת ל-, היא תדע שהיא נמצאת בתא הראשון בסרט, ולכן היא
תפעל על פי הכללים הבאים:
- אם במקור הייתה אמורה ללכת שמאלה,
אז תישאר באותו המקום (ולא
תפנה שמאלה).
- אם אמורה להחליף את האות באות אז תחליף את באות .
סיום:
אם הגיעה למצב מקבל אז צריכה לסמן את המקום ב-$, לנוע שמאלה עד התחלת הסרט,
שם היא תמצא אות השייכת ל-.
את אות זו היא תחליף אותה באות המתאימה מ-,
תנוע חזרה ימינה עד לסימן ה-$ ותעצור.
בהינתן , נגדיר את
כך:
פונקצית המעברים :
- מעבר התחלתי:
- - אם לא נמצאים על האות הראשונה, מבצעים את מה
שביצעה המכונה המקורית.
- אם כך ש
אז - אם נמצאים באות
הראשונה, והתנועה המקורית הייתה שמאלה או עצירה, אז נשארים במקום. בכל מקרה,
האות שכותבים שייכת ל-.
- אם אז - אם נמצאים באות הראשונה, והתנועה המקורית הייתה ימינה, אז
נעים ימינה, אבל האות שכותבים היא מ-.
- - אם המכונה הקודמת עצרה, ולא על התו הראשון,
אז מחליפים את התו ב- ועוברים למצב שממנו מתחילים לנוע שמאלה.
- - נעים שמאלה בלי לשנות כלום.
- - מחליפים את האות מ- לאות מ- ועוברים למצב שממנו
מתחילים לנוע ימינה.
- - נעים ימינה בלי לשנות כלום.
- - עצירה.
- - אם החישוב המקורי נעצר על האות הראשונה, אז
עוצרים באותו המקום, ומחזירים כפלט מילה ריקה.
החלק הראשון
בבקשה