תורת החישוביות/מכונת טיורינג: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירה |
הגדרה |
||
שורה 6:
==הגדרה==
באופן פורמלי, מכונת טיורינג מורכבת מ-7 מרכיבים שונים. לפי התיאור לעיל קל להבחין במספר מרכיבים: מצבי הבקרה השונים, סט האותיות שניתן לכתוב על הסרט וה"תוכנה" של המכונה - הדרך בה בתוכנה משנה מצבים בהתאם לזיכרון ולמצב הנוכחי. נגדיר כעת את כלל המרכיבים באופן מדוייק.
מתמטית, מכונת טיורינג ('''מ"ט''') <math>M</math> מוגדרת על-ידי השביעייה הבאה:
<center> <math>M=(Q,q_0,F,\Gamma,\Sigma, \sqcup, \delta)</math></center>
כאשר:
* <math>Q</math> - קבוצת כלל מצבי הבקרה (קבוצה זו אינה ריקה).
* <math>q_0</math> - המצב ההתחלתי. בעת תחילת החישוב, המכונה נמצאת במצב זה. <math>(q_0 \in Q)</math>
* <math>F</math> - קבוצת '''מצבים סופיים'''. כאשר המכונה עוברת לאחד ממצבים אלו, המכונה עוצרת והחישוב מסתיים. <math>(F\subseteq Q)</math>
* <math>\Gamma</math> - קבוצת כל האותיות אותן ניתן לכתוב על סרט הזיכרון (נקרא: '''אלפבית הזיכרון'''). קבוצה זו אינה ריקה.
* <math>\Sigma</math> - '''אלפבית הקלט''', קבוצה (לא ריקה) של כל האותיות המגדירות קלט תקין עבור המכונה. <math>(\Sigma \subsetneqq \Gamma)</math>
* <math>\sqcup</math> - סימן מיוחד המייצג "רווח" (blank), כלומר, תא זיכרון ריק שלא כתוב בו כלום. <math>\sqcup \in \Gamma \smallsetminus \Sigma</math>, כלומר הקלט לא יכול להכיל רווחים.
* <math>\delta</math> - '''פונקציית המעברים''', השיטה שבה המכונה מחליפה את המצבים. לכל (מצב נוכחי שאינו סופי, אות נוכחית) הפונקציה מגדירה (מצב חדש, אות חדשה, תזוזת הראש):
<center><math>\delta: \left((Q\smallsetminus F)\times\Gamma\right) \to \left( Q\times\Gamma\times\{R,L,S\} \right )</math></center>
[[קטגוריה:תורת החישוביות]]
| |||