תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
מאין תקציר עריכה |
||
שורה 15:
<center> <math>M=\langle Q,q_0,F,\Gamma,\Sigma, b, \delta \rangle</math></center>
כאשר:
* <math>Q</math>
* <math>q_0 \in Q</math>
* <math>F \subseteq Q</math>
* <math>\Gamma</math>
* <math>\Sigma \subsetneqq \Gamma</math>
* <math>b \in \Gamma \smallsetminus \Sigma</math>
* <math>\delta</math>
<math>\delta: (Q\smallsetminus F)\times\Gamma \to
==מהלך חישוב==
שורה 29:
בכל צעד חישוב הראש קורא את האות שעליה הוא מצביע. נניח שהראש קרא את האות <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> נאמר שהמכונה עצרה. ה'''פלט של החישוב''' הינו כל מה שנמצא על הסרט, בין התא הראשון של הסרט והראש הכותב, כלומר, כל מה שמשמאל לראש.
| |||