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

 

==מבוא==

נגדיר מצב קצה: נניח שראש המכונה נמצא בתא השמאלי ביותר (בתא הראשון), והמכונה צריכה להזיז את הראש שמאלה (הפונקציה <math>\delta</math> החזירה תזוזה L, שמאלה). במקרה זה נגדיר שהראש נשאר במקומו (במקום לזוז שמאלה), והחישוב ממשיך כרגיל. לעיתים מכונה מקרה זה בשם '''נסיון נפילה מן הסרט'''.

 

נבנה מכונת-טיורינג שמוסיפה את התו "0" לתחילת הקלט, כלומר, עבור הקלט <math>x_1x_2\cdots x_n</math> הפלט יהיה <math>0x_1x_2\cdots x_n</math>. נניח כי הקלט הינו בינארי, <math>\Sigma=\{0,1\}</math>. למכונה יש למעשה שתי משימות: האחת, להוסיף "0" בתור התו הראשון, והשניה "להזיז" את הקלט מיקום אחד ימינה על סרט הזיכרון. נשתמש בשלושה מצבים: המצב הראשון "ישתול" את התו '0' בתחילה, ו"יזכור" מה היה רשום בתא לפני שדרסנו אותו. שני המצבים הבאים יסמלו את התו שאנחנו "זוכרים", ותפקידם להעתיק את התו צעד אחד ימינה, כאשר כעת "זוכרים" את התו שנדרס בצעד זה, וחוזר חלילה. מצב רביעי יציין סיום של המכונה, ואליו נגיע כאשר העתקנו את המידע ש"זכרנו" אל תא ריק.