תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
דוגמא |
|||
שורה 58:
העמודות הינן האות הנוכחית, והשורות הינו המצב הנוחכי. ערך כל תא מסמל את המצב החדש אליו אנו עוברים, האות אותה אנו כותבים וכיוון תנועת הראש. למשל <math>\delta(start,0)=(mem_0,0,R)</math>. נשים לב שהמצב התחילי start והמצב <math>mem_0</math> מבצעים את אותה פעולה, ואפשר לאחד אותם למצב יחיד (ואכן, בתחילת הריצה אנחנו "זוכרים" לכתוב 0, בדיוק כאמור במצב <math>mem_0</math>).
==קונפיגורציה==
נשים לב שעבור מ"ט נתונה, כל צעד חישוב נקבע בצורה יחידה על-ידי האינפורמציה הבאה:
# תוכן הסרט
#מצב הבקרה
#מיקום ראש הסרט
נשים לב שכל המידע לעיל הינו מידע '''סופי''': סרט הזיכרון הינו סופי מכיוון שיש מקום שממנו ואילך כל התאים ריקים; מצב הבקרה ומיקום הראש הם נתונים סופים גם כן (יש מספר סופי של מצבים, ובכל רגע נתון הראש נמצא במיקום מסויים, שניצן לייצגו כמספר).
באופן פורמלי, נגדיר '''קונפיגורציה''' בתור מצב המכונה ''בתחילת''' צעד החישוב.
{{הגדרה|תוכן=קונפיגורציה של מ"ט 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>
# <math>i \in \mathbb{N}</math> מיקום הראש יחסית לקצה הסרט, <math>1\le i \le m</math>
כאשר m הוא המקסימום בין אורך הקלט לבין המקום המקסימלי שהראש כתב בו (או לחלופין, הזמן מתחילת החישוב).}}
[[קטגוריה:תורת החישוביות]]
| |||