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

# קונפיגורציה <math>C'</math> נקראת '''עוקבת''' לקונפיגורציה <math>C</math> אם המכונה M עוברת בצעד אחד מ<math>C</math> ל-<math>C'</math>. נסמן <math>C \vdash_M C'</math>. <br />נשים לב: לקונפיגורציה סופית '''אין''' קונפיגורציה עוקבת.

# '''סדרת החישוב''' של מכונה 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>. <br> קל לראות כי לכל קלט x מוגדרת בדיוק סדרת חישוב אחת עבור המכונה M.

# אם M עוצרת על x אז הפלט מוגדר: תהי <math>(\alpha,q,i)</math> הקונפיגורציה הסופית בסדרת החישוב של M על x, אזי הפלט הוא <math>\alpha_1,\alpha_2,\ldots,\alpha_{i-1}</math>.<br> אם הראש בקצה <math>(i=1)</math> אזי הפלט הוא המילה הריקה <math>\varepsilon</math>.<br> אם M אינה עוצרת על x הפלט אינו מוגדר.