תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דוגמא |
מ ←קונפיגורציה: עיצוב |
||
שורה 66:
באופן פורמלי, נגדיר '''קונפיגורציה''' בתור מצב המכונה '''בתחילת''' צעד החישוב.
{{הגדרה|תוכן='''קונפיגורציה''' של מ"ט M הינה השלשה <math>(\alpha, q,i)</math> כך ש
#<math>\alpha=\alpha_1\alpha_2\ldots\alpha_m</math> מחרוזת של m אותיות מעל <math>\Gamma</math>
#<math>q\in Q</math>
שורה 77:
{{דוגמה|תוכן=קונפיגורציה סופית היא כל קונפיגורציה <math>(\alpha, q,i)</math> עבורה <math>q\in F</math>}}
-->
לכל מ"ט M על קלט x, '''הקונפיגורציה ההתחלתית''' היא <math>C_0=(x, q_0,1)</math>. '''קונפיגורציה סופית''' היא כל קונפיגורציה <math>(\alpha, q,i)</math> עבורה <math>q\in F</math>.
{{תרגיל|יישור=ימין|
|