תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
|||
שורה 13:
מתמטית, מכונת טיורינג ('''מ"ט''') <math>M</math> מוגדרת על-ידי השביעייה הבאה:
<center> <math>M=
כאשר:
* <math>Q</math> - קבוצת כלל מצבי הבקרה (קבוצה זו אינה ריקה).
* <math>q_0 \in Q</math> - המצב ההתחלתי. בעת תחילת החישוב, המכונה נמצאת במצב זה.
* <math>F \subseteq Q</math> - קבוצת '''מצבים סופיים'''. כאשר המכונה עוברת לאחד ממצבים אלו, המכונה עוצרת והחישוב מסתיים.
* <math>\Gamma</math> - קבוצת כל האותיות אותן ניתן לכתוב על סרט הזיכרון (נקרא: '''אלפבית הזיכרון'''). קבוצה זו אינה ריקה.
* <math>\Sigma \subsetneqq \Gamma</math> - '''אלפבית הקלט''', קבוצה (לא ריקה) של כל האותיות המגדירות קלט תקין עבור המכונה.
* <math>b \
* <math>\delta</math> - '''פונקציית המעברים''', השיטה שבה המכונה מחליפה את המצבים. לכל (מצב נוכחי שאינו סופי, אות נוכחית) הפונקציה מגדירה (מצב חדש, אות חדשה, תזוזת הראש):
<center><math>\delta:
==מהלך חישוב==
|