תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
הגדרה |
מהלך חישוב |
||
שורה 20:
<center><math>\delta: \left((Q\smallsetminus F)\times\Gamma\right) \to \left( Q\times\Gamma\times\{R,L,S\} \right )</math></center>
==מהלך חישוב==
[[קובץ:TM initial.png|שמאל|ממוזער|250px|מכונת טיורינג בתחילת החישוב עבור הקלט "abc"]]
בתחילת החישוב, סרט הזיכרון מכיל את מילת הקלט, כאשר האות הראשונה של הקלט נמצאת בקצה הסרט. כל שאר התאים בסרט (התאים הריקים) מכילים את התו המיוחד '<math>\sqcup</math>', (כך ניתן לדעת היכן מסתיים הקלט). המצב ההתחלתי הוא <math>q_0</math> והראש הקורא/כותב נמצא בא הראשון של הסרט (מונח על האות הראשונה של הקלט).
בכל צעד חישוב הראש קורא את האות שעליה הוא מצביע. נניח שהראש קרא את האות <math>a</math>, והמכונה נמצאת במצב בקרה (לא סופי) <math>q</math>, אזי אם <math>\delta(q,a)=(q',b,d)</math> המכונה תחליף את האות <math>a</math> באות <math>b</math>
, תזיז את הראש בהתאם לכיוון <math>d\in\{R,L,S\}</math> (כאשר L=שמאלה, R=ימינה ו-S=השאר במקום), ותעבור למצב בקרה חדש <math>q'</math>. לאחר מכן מתחיל צעד החישוב הבא.
עצירה: אם המכונה עברה למצב בקרה סופי <math>\bar{q}\in F</math> נאמר שהמכונה עצרה. ה'''פלט של החישוב''' הינו כל מה שנמצא על הסרט, בין התא הראשון של הסרט והראש הכותב, כלומר, כל מה שמשמאל לראש.
נגדיר מצב קצה: נניח שראש המכונה נמצא בתא השמאלי ביותר (בתא הראשון), והמכונה צריכה להזיז את הראש שמאלה (הפונקציה <math>\delta</math> החזירה תזוזה L, שמאלה). במקרה זה נגדיר שהראש נשאר במקומו (במקום לזוז שמאלה), והחישוב ממשיך כרגיל. לעיתים מכונה מקרה זה בשם '''נסיון נפילה מן הסרט'''.
[[קטגוריה:תורת החישוביות]]
| |||