תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←קונפיגורציה: עיצוב |
←קונפיגורציה: הרחבה |
||
שורה 84:
<center><math>(0010,mem_1,4) \to (0011\sqcup,mem_1,5) \to (00110\sqcup,done,6)</math>.</center>
הקונפיגורציה האחרונה היא סופית,כי <math>done</math> הוא מצב סופי. }}
{{הגדרה|
תוכן=
#קונפיגורציה <math>C'</math> נקראת '''עוקבת''' לקונפיגורציה <math>C</math> אם המכונה M עוברת בצעד אחד מ<math>C</math> ל-<math>C'</math>. נסמן <math>C \vdash_M C'</math>.
#'''סדרת החישוב''' של מכונה M על קלט x היא סדרה סופית או אינסופית של קונפיגורציות <math>C_0, C_1, C_2, \ldots</math> כך ש-<math>C_0=(x,q_0,1)</math> הקונפיגורציה ההתחלתית, וכן לכל <math>i \ge 0</math>, אם <math>C_i</math> אינה קונפיגורציה סופית אזי מתקיים <math>C_i \vdash_M C_{i+1}</math>.}}
נשים לב: לקונפיגורציה סופית '''אין''' קונפיגורציה עוקבת.
[[קטגוריה:תורת החישוביות]]
| |||