תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←קונפיגורציה: הרחבה |
←קונפיגורציה: הרחבה |
||
שורה 65:
נשים לב שכל המידע לעיל הינו מידע '''סופי''': סרט הזיכרון הינו סופי מכיוון שיש מקום שממנו ואילך כל התאים ריקים; מצב הבקרה ומיקום הראש הם נתונים סופים גם כן (יש מספר סופי של מצבים, ובכל רגע נתון הראש נמצא במיקום מסויים, שניצן לייצגו כמספר).
באופן פורמלי, נגדיר '''קונפיגורציה''' בתור מצב המכונה '''בתחילת''' צעד החישוב.
{{הגדרה|תוכן=קונפיגורציה של מ"ט M הינה השלשה <math>(\alpha, q,i)</math> כך ש
#<math>\alpha=\alpha_1\alpha_2\ldots\alpha_m</math> מחרוזת של m אותיות מעל <math>\Gamma</math>
שורה 86:
===הגדרות===
# קונפיגורציה <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>.
▲#קונפיגורציה <math>C'</math> נקראת '''עוקבת''' לקונפיגורציה <math>C</math> אם המכונה M עוברת בצעד אחד מ<math>C</math> ל-<math>C'</math>. נסמן <math>C \vdash_M C'</math>.
#אם סדרת החישובת סופית, ואורכה m, נאמר שM רצה על הקלט x‏ m-1 צעדים ואז עוצרת (לחלופין: M עוצרת על x לאחר m-1 צעדים). אם הסדרה אינה סופית נאמר שM אינה עוצרת על x.
▲#'''סדרת החישוב''' של מכונה 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>.}}
# אם 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 הפלט אינו מוגדר.
[[קטגוריה:תורת החישוביות]]
| |||