תורת החישוביות/מכונת טיורינג

מכונת טיורינג היא מודל מתמטי המדמה את מכונת החישוב שאנו מכירים. למרות פשטותה של המכונה, ניתן להראות כי בכוחה לחשב כל אלגוריתם או תוכנית הכתובה בשפת תכנות נפוצה כגון C או פסקל.

מבוא

איור של "מכונת טיורינג" עם סרט זיכרון אינסופי

ניתן לחשוב על מכונת טיורינג כעל מכונת מצבים פשוטה (בקר / "אוטומט") שבכל צעד חישוב יכול לשנות את מצבו בהתאם לקלט שלו. למכונה יש גישה לסרט זיכרון - סרט אינסופי של תאים, ובכל תא כתובה אות יחידה. למכונה יש "ראש קורא/כותב" הממוקם על אחד תאי הזיכרון. בכל צעד, בהתאם למצב הנוכחי של המכונה ולאות הכתובה בתא עליו מצביע הראש הקורא/כותב, המכונה יכולה להחליט מה לעשות: לאיזה מצב חדש לעבור, איזו אות לכתוב בתא הזיכרון עליו עומד הראש הקורא/כותב, והאם להזיז את הראש (צעד אחר ימינה או שמאלה).

להרחבה בנושא מכונות מצבים, ראו אוטומטים ושפות פורמליות.

הגדרה

באופן פורמלי, מכונת טיורינג מורכבת מ-7 מרכיבים שונים. לפי התיאור לעיל קל להבחין במספר מרכיבים: מצבי הבקרה השונים, סט האותיות שניתן לכתוב על הסרט וה"תוכנה" של המכונה - הדרך בה בתוכנה משנה מצבים בהתאם לזיכרון ולמצב הנוכחי. נגדיר כעת את כלל המרכיבים באופן מדוייק.

מתמטית, מכונת טיורינג (מ"ט) $M$ מוגדרת על-ידי השביעייה הבאה:

$M=(Q,q_0,F,\Gamma,\Sigma, \sqcup, \delta)$

כאשר:

• $Q$ - קבוצת כלל מצבי הבקרה (קבוצה זו אינה ריקה).
• $q_0$ - המצב ההתחלתי. בעת תחילת החישוב, המכונה נמצאת במצב זה. $(q_0 \in Q)$
• $F$ - קבוצת מצבים סופיים. כאשר המכונה עוברת לאחד ממצבים אלו, המכונה עוצרת והחישוב מסתיים. $(F\subseteq Q)$
• $\Gamma$ - קבוצת כל האותיות אותן ניתן לכתוב על סרט הזיכרון (נקרא: אלפבית הזיכרון). קבוצה זו אינה ריקה.
• $\Sigma$ - אלפבית הקלט, קבוצה (לא ריקה) של כל האותיות המגדירות קלט תקין עבור המכונה. $(\Sigma \subsetneqq \Gamma)$
• $\sqcup$ - סימן מיוחד המייצג "רווח" (blank), כלומר, תא זיכרון ריק שלא כתוב בו כלום. $\sqcup \in \Gamma \smallsetminus \Sigma$, כלומר הקלט לא יכול להכיל רווחים.
• $\delta$ - פונקציית המעברים, השיטה שבה המכונה מחליפה את המצבים. לכל (מצב נוכחי שאינו סופי, אות נוכחית) הפונקציה מגדירה (מצב חדש, אות חדשה, תזוזת הראש):

$\delta: \left((Q\smallsetminus F)\times\Gamma\right) \to \left( Q\times\Gamma\times\{R,L,S\} \right )$

מהלך חישוב

מכונת טיורינג בתחילת החישוב עבור הקלט "abc"

בתחילת החישוב, סרט הזיכרון מכיל את מילת הקלט, כאשר האות הראשונה של הקלט נמצאת בקצה הסרט. כל שאר התאים בסרט (התאים הריקים) מכילים את התו המיוחד '$\sqcup$', (כך ניתן לדעת היכן מסתיים הקלט). המצב ההתחלתי הוא $q_0$ והראש הקורא/כותב נמצא בתא הראשון של הסרט (מונח על האות הראשונה של הקלט).

בכל צעד חישוב הראש קורא את האות שעליה הוא מצביע. נניח שהראש קרא את האות $a$, והמכונה נמצאת במצב בקרה (לא סופי) $q$, אזי אם $\delta(q,a)=(q',b,d)$ המכונה תחליף את האות $a$ באות $b$ , תזיז את הראש בהתאם לכיוון $d\in\{R,L,S\}$ (כאשר L=שמאלה, R=ימינה ו-S=השאר במקום), ותעבור למצב בקרה חדש $q'$. לאחר מכן מתחיל צעד החישוב הבא.

עצירה: אם המכונה עברה למצב בקרה סופי $\bar{q}\in F$ נאמר שהמכונה עצרה. הפלט של החישוב הינו כל מה שנמצא על הסרט, בין התא הראשון של הסרט והראש הכותב, כלומר, כל מה שמשמאל לראש.

נגדיר מצב קצה: נניח שראש המכונה נמצא בתא השמאלי ביותר (בתא הראשון), והמכונה צריכה להזיז את הראש שמאלה (הפונקציה $\delta$ החזירה תזוזה L, שמאלה). במקרה זה נגדיר שהראש נשאר במקומו (במקום לזוז שמאלה), והחישוב ממשיך כרגיל. לעיתים מכונה מקרה זה בשם נסיון נפילה מן הסרט.

דוגמה

נבנה מכונת-טיורינג שמוסיפה את התו "0" לתחילת הקלט, כלומר, עבור הקלט $x_1x_2\cdots x_n$ הפלט יהיה $0x_1x_2\cdots x_n$. נניח כי הקלט הינו בינארי, $\Sigma=\{0,1\}$. למכונה יש למעשה שתי משימות: האחת, להוסיף "0" בתור התו הראשון, והשניה "להזיז" את הקלט מיקום אחד ימינה על סרט הזיכרון. נשתמש בשלושה מצבים: המצב הראשון "ישתול" את התו '0' בתחילה, ו"יזכור" מה היה רשום בתא לפני שדרסנו אותו. שני המצבים הבאים יסמלו את התו שאנחנו "זוכרים", ותפקידם להעתיק את התו צעד אחד ימינה, כאשר כעת "זוכרים" את התו שנדרס בצעד זה, וחוזר חלילה. מצב רביעי יציין סיום של המכונה, ואליו נגיע כאשר העתקנו את המידע ש"זכרנו" אל תא ריק.

באופן פורמלי, מרכיבי המכונה הם:

• $Q=\{start , mem_0, mem_1, done\}$
• $q_0 = start$
• $F=\{ done \}$
• $\Gamma=\{0,1,\sqcup\}$
• $\Sigma = \{0,1\}$

ופונקצית המעברים מוגדרת להלן

$\sqcup$	1	0	$\delta(\cdot,\cdot)$
$done, 0, R$	$mem_1,0,R$	$mem_0,0,R$	$start$
$done,0,R$	$mem_1,0,R$	$mem_0,0,R$	$mem_0$
$done,1,R$	$mem_1,1,R$	$mem_0,1,R$	$mem_1$

העמודות הינן האות הנוכחית, והשורות הינו המצב הנוכחי. ערך כל תא מסמל את המצב החדש אליו אנו עוברים, האות אותה אנו כותבים וכיוון תנועת הראש. למשל $\delta(start,0)=(mem_0,0,R)$. נשים לב שהמצב התחילי start והמצב $mem_0$ מבצעים את אותה פעולה, ואפשר לאחד אותם למצב יחיד (ואכן, בתחילת הריצה אנחנו "זוכרים" לכתוב 0, בדיוק כאמור במצב $mem_0$).

קונפיגורציה

נשים לב שעבור מ"ט נתונה, כל צעד חישוב נקבע בצורה יחידה על-ידי האינפורמציה הבאה:

1. תוכן הסרט
2. מצב הבקרה
3. מיקום ראש הסרט

נשים לב שכל המידע לעיל הינו מידע סופי: סרט הזיכרון הינו סופי מכיוון שיש מקום שממנו ואילך כל התאים ריקים; מצב הבקרה ומיקום הראש הם נתונים סופים גם כן (יש מספר סופי של מצבים, ובכל רגע נתון הראש נמצא במיקום מסויים, שניצן לייצגו כמספר).

באופן פורמלי, נגדיר קונפיגורציה בתור מצב המכונה בתחילת צעד החישוב.

הגדרה: קונפיגורציה של מ"ט M הינה השלשה $(\alpha, q,i)$ כך ש $\alpha=\alpha_1\alpha_2\ldots\alpha_m$ מחרוזת של m אותיות מעל $\Gamma$ $q\in Q$ $i \in \mathbb{N}$ מיקום הראש יחסית לקצה הסרט, $1\le i \le m$ כאשר m הוא המקסימום בין אורך הקלט לבין המקום המקסימלי שהראש עבר בו (או לחלופין, הזמן מתחילת החישוב).

לכל מ"ט M על קלט x, הקונפיגורציה ההתחלתית היא $C_0=(x, q_0,1)$. קונפיגורציה סופית היא כל קונפיגורציה $(\alpha, q,i)$ עבורה $q\in F$.

תרגיל : רשום את סדרת הקונפיגורציות של המכונה בדוגמא לעיל על הקלט 0110
הקונפיגורציה ההתחלתית היא $(0110,start,1)$. לאחר צעד חישוב אחד המכונה בקונפיגורציה $(0110,mem_0,2)$ ובצעד החישוב הבא הקונפיגורציה תהיה $(0010,mem_1,3)$, ולאחר מכן סדרת הקונפיגורציות היא $(0010,mem_1,4) \to (0011\sqcup,mem_1,5) \to (00110\sqcup,done,6)$. הקונפיגורציה האחרונה היא סופית,כי $done$ הוא מצב סופי.

הגדרות

1. קונפיגורציה $C'$ נקראת עוקבת לקונפיגורציה $C$ אם המכונה M עוברת בצעד אחד מ$C$ ל-$C'$. נסמן $C \vdash_M C'$.
   נשים לב: לקונפיגורציה סופית אין קונפיגורציה עוקבת.
2. סדרת החישוב של מכונה M על קלט x היא סדרה סופית או אינסופית של קונפיגורציות $C_0, C_1, C_2, \ldots$ כך ש-$C_0=(x,q_0,1)$ הקונפיגורציה ההתחלתית, וכן לכל $i \ge 0$, אם $C_i$ אינה קונפיגורציה סופית אזי מתקיים $C_i \vdash_M C_{i+1}$.
   קל לראות כי לכל קלט x מוגדרת בדיוק סדרת חישוב אחת עבור המכונה M.
3. אם סדרת החישובת סופית, ואורכה m, נאמר שM רצה על הקלט x‏ m-1 צעדים ואז עוצרת (לחלופין: M עוצרת על x לאחר m-1 צעדים). אם הסדרה אינה סופית נאמר שM אינה עוצרת על x.
4. אם M עוצרת על x אז הפלט מוגדר: תהי $(\alpha,q,i)$ הקונפיגורציה הסופית בסדרת החישוב של M על x, אזי הפלט הוא $\alpha_1,\alpha_2,\ldots,\alpha_{i-1}$.
   אם הראש בקצה $(i=1)$ אזי הפלט הוא המילה הריקה $\varepsilon$.
   אם M אינה עוצרת על x הפלט אינו מוגדר.

מושג הקונפיגורציה יאפשר לנו לטעון ולהוכיח (באופן פורמלי) נכונות של טענות לגבי מכונות טיורינג. לדוגמא, נוכיח נכונות המכונה בדוגמא להזזת הקלט, כלומר נוכיח את הטענה: "לכל קלט x הפלט הוא 0x". ההוכחה מתבצעת באינדוקציה על אורך הקלט m. נניח כי סדרת החישוב היא $C_0\vdash C_1\vdash \cdots C_{m+1}$ ומתקיים:

$C_0=(x,q_0,1)$

$\forall 0<i\le m, C_i=(0x_1x_2..x_{i-1}x_{i+1}..x_m,mem_{x_i},i+1)$

$C_{m+1}=(0x_1x_2..x_m\sqcup,done,m+2)$

הפרק הקודם: מבוא

מכונת טיורינג

הפרק הבא: שקילות מודלי חישוב