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

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

קידוד מ"ט על-ידי מחרוזת בינארית

נתונה מ״ט $M=(Q,q_{0},F,\Gamma ,\Sigma ,\sqcup ,\delta )$. בלי הגבלת הכלליות (למשל, ע״י החלפת שמות) ניתן להניח

• $Q=\{1,2,3,\ldots \}$ כאשר המצב ההתחלתי $q_{0}=1$.
• $F=\{2,3\}$ שכן לא נדרשים יותר משני מצבים סופיים (אחד לקבלה, אחד לדחייה)
• $\Sigma =\{1,2,3,\ldots ,|\Sigma |\}$
• $\Gamma =\{1,2,3,\ldots ,|\Gamma |\}$
• $\sqcup =|\Gamma |$

נרצה לתאר את המכונה (כלומר, כל אחד ממרכיביה השונים) על-ידי מחרוזת בינארית. נתחיל בקידוד המעברים:

$\delta (q,a)=\{p,b,d\}$

(כאשר הכיוון d נתון על ידי: $L=1,R=2,S=3$) יקודד על ידי המחרוזת

$1^{q}01^{a}01^{p}01^{b}01^{d}$

כלומר q פעמים הספרה 1, ולאחריה 0; לאחר מכן a פעמים הספרה 1 ולאחריה 0 יחיד, וכן הלאה.

נשים לב שאין שני אפסים רצופים!

קידוד המכונה $M=(Q,q_{0},F,\Gamma ,\Sigma ,\sqcup ,\delta )$ נתון על-ידי:

$1^{|Q|}01^{|\Gamma |}01^{|\Sigma |}0\delta _{1}00\delta _{2}00\ldots \delta _{last}000$

כאשר $\delta _{i}$ הינו הקידוד של המעבר ה-i, כאשר נניח שהקידודים מסודרים בסדר כלשהו (קידוד המכונה אינו חד־חד ערכי; סדר שונה של מעברים יאפשר קידוד אותה המכונה בשני אופנים שונים). נשים לב:

• ראשית אנו מקודדים את הפרמטרים של המכונה, המפרט את כלל המצבים לפי ההנחות לעיל
• לאחר מכן שני אפסים מעידים על סוף הקידוד של מעבר אחר ותחילת המעבר הבא. מכיוון שבקידוד מעבר לעולם אין שני אפסים רצופים, הגדרה זו אינה דו־משמעית.
• קיימים לכל היותר $|Q-F|\cdot |\Gamma |$ מעברים שונים.
• שלושה אפסים רצופים מציינים את סוף קידוד המכונה השלמה.

תרגיל : וודא שהקידוד לעיל מכיל את כל המרכיבים של M: בדוק שאכן ניתן לדעת מהו כל אחד מהמרכיבים של M רק מקריאת המחרוזת ומההנחות לעיל, ושמתקבלת מכונה יחידה מכל מחרוזת (אין דו משמעות).

תרגיל : קודד למחרוזת בינארית את המכונה המתוארת בדוגמא שבפרק מכונות-טיורנג.

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

לכל מחרוזת נתונה, קל לבדוק האם היא מייצגת מכונת טיורינג או שהיא קידוד לא־חוקי. יותר מכך – קיים אלגוריתם שבודק האם מחרוזת מסוימת היא קידוד חוקי או לא, ומכאן שקיימת מכונת טיורינג שמקבלת כקלט מחרוזת ומקבלת אם ורק אם המחרוזת היא קידוד חוקי של מ״ט כלשהי. מכונה כנ״ל יכולה "לשאוב" את כל המידע הנחוץ (מספר המצבים וכו') על המכונה המקודדת במחרוזת הקלט.

סימון

הגדרה: הקידוד של מ״ט M יסומן $\langle M\rangle$

דוגמה: משמעות הקבוצה $\{\langle M\rangle \mid M{\text{ does XXXX}}\}$, היא אוסף כל המחרוזות (חוקיות או לא) שהמכונות שהן מקודדות, מבצעות XXXX.

קונפיגורציות וקידוד קופניגורציות

כעת נראה כיצד ניתן לקודד למחרוזת בינארית קונפיגורציות. כזכור, קונפיגורציה היא אוסף המידע המגדיר את מצב המכונה M בתחילת צעד חישוב. ראינו בפרק קודם שקונפיגורציה מכילה כמות מידע סופית ועל כן ניתן לקודד אותה למחרוזת בינארית (באורך סופי). הקונפיגורציה $C=(a_{1}a_{2}\ldots a_{k},q,i)$ תקודד באופן הבא

$\langle C\rangle =1^{a_{1}}01^{a_{2}}0\ldots 1^{a_{i-1}}\underbrace {001^{q}} _{\text{head}}01^{a_{i}}01^{a_{i+1}}\ldots 01^{a_{k}}$

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

תרגיל : מה משמעות הקונפיגורציה $\langle C\rangle =001$?
הקידוד מתחיל בשני אפסים, כלומר, הראש מצביע על התא הראשון בסרט. מצב המכונה הוא מצב "1" (המצב ההתחלתי). פרט לכך, כל שאר התאים ריקים! הקונפיגורציה המתקבלת היא $C=(\varepsilon ,q_{0},1)$.

המכונה האוניברסלית

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

הפונקציה העוקבת

הגדרה: הפונקציה העוקבת NEXT()‎ מוגדרת: קידוד הקונפיגורציה העוקבת לC ${\mathsf {NEXT}}(\langle M\rangle ,\langle C\rangle )=$

NEXT()‎ היא פונקציה חלקית (אינה מוגדרת על כל התחום):

• ייתכן שהקידוד $\langle C\rangle$ אינו חוקי
• ייתכן ש$\langle C\rangle$ אינו מתאים למכונה M (למשל, משתמש באות שאינה באלפבית של M)
• ייתכן שC היא קונפיגורציה סופית, ואין לה קונפיגורציה עוקבת.

טענה: הפונקציה NEXT()‎ ניתנת לחישוב על-ידי מכונת טיורינג

הקלט של הפונקציה הוא $\langle M\rangle ,\langle C\rangle$, כלומר שתי המחרוזות משורשרות זו לזו. ראינו איך מקודדים את M ואת C, אבל איך המכונה יודעת מתי מסתיים הקידוד M ומתי מתחיל C ? במילים אחרות - איך מקודדים את הפסיק? במקרה זה התשובה פשוטה, מכיוון שהקידוד $\langle M\rangle$ מסתיים בשלושה אפסים רצופים, נקודת הגבול בין שתי המחרוזות מוגדרת היטב. במקרים אחרים, ייתכן שהקלט אינו מכיל הפרדה פנימית, למשל, אם הקלט הוא קידוד של מספר קונפיגורציות $\langle C_{0}\rangle \langle C_{1}\rangle \langle C_{2}\rangle$. במקרה זה ניתן לקודד את ה"פסיק" בתור מחרוזת של, למשל, ארבעה אפסים רצופים, ולדעת להפריד בין מחרוזות הקלט השונות. פתרון אחר הוא להפריד על-ידי הספרה "2" (ואז מחרוזת הקלט אינה בינארית כי אם טרינרית, אבל החלקים ה"מעניינים" של הקלט מקודדים בצורה בינארית). בהמשך נניח כי קיים קידוד כלשהו לסימן הפסיק, והמכונה מסוגלת להפריד בין חלקים שונים של הקלט, מבלי להכנס לקידוד הספציפי

הוכחה (להלן האלגוריתם של המכונה המתאימה):

1. המכונה בודקת שהקלט מהווה קידוד תקין. (אם לא תקין - המכונה נכנסת ללולאה אינסופית, והפלט אינו מוגדר).
2. אם C אינה קונפיגורציה סופית, נחשב את הקונפיגורציה העוקבת באופן הבא:
   1. מעבר על $\langle C\rangle$ וחילוץ המצב q בו המכונה M נמצאת, ואת האות a אותה הסרט רואה.
   2. מעבר על $\langle M\rangle$ וחילוץ המעבר $\delta (q,a)$ (הקידוד של מעבר זה מתחיל ב$001^{q}01^{a}$ כך שקל למצוא אותו על-ידי השוואה עם הקידוד $\langle C\rangle$ החל מהמקום בו קיימים שני אפסים..).
   3. מחלצים את (p,b,d) מהמעבר ומעדכנים את הקונפיגורציה: כותבים את האות b במקום a (שים לב: כדי לשנות אות צריך רק לשנות את מספר ה"1"ים בתא המתאים!); משנים את המצב לp ו"מזיזים" את המיקום של הראש לפי הצורך לפני התא המתאים.
3. מזיזים את הקונפיגורציה החדשה לתחילת המסרט, מזיזים את הראש לסופה ועוצרים (כלומר: הפלט הוא הקונפיגורציה המעודכנת).

הפונקציה האוניברסלית

הגדרה: הפונקציה האוניברסלית היא $U(\langle M\rangle ,x)=f_{M}(x)$

כלומר, הפונקציה האוניברסלית על קלט קידוד $\langle M\rangle$ ומחרוזת x, מחשבת כפלט את תוצאת הריצה של המכונה M (המוגדרת על-ידי המחרוזת $\langle M\rangle$) על המחרוזת x. אם M לא עוצרת על x אזי $U(\langle M\rangle ,x)$ אינו מוגדר (U היא פונקציה חלקית).

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

מכונה המחשבת את הפונקציה האוניברסלית U נקראת המכונה האוניברסלית ובספרים רבים מסומנת $M_{U}$. קיימות מספר מכונות המחשבות את הפונקציה האוניברסלית ולהן מספר שונה של מצבים וגודל אלפבית. למשל מרווין מינסקי הראה ב-1962 כי קיימת מכונה אוניברסלית עם 7 מצבים בלבד ואלפבית בגודל 4, ולאחר מכן נתגלו מכונות אוניברסליות עם 5 מצבים ואלפבית בגודל 5; 4 מצבים ואלפבית בגודל 6; 3 מצבים ואלפבית בגודל 9; ואפילו 2 מצבים בלבד ואלפבית בגודל 18.

הוכחה: נניח מכונה בעלת שני סרטים, ונתאר את פעולה על הקלט $(\langle M\rangle ,x)$:

1. אם $\langle M\rangle$ אינו קידוד תקין - עצור מייד עם הפלט $\varepsilon$.
2. אחרת - כתוב על הסרט השני את הקונפיגורציה ההתחלתית של M על x.
3. בצע בלולאה:
   כל עוד הקונפיגורציה C המקודדת בסרט השני אינה סופית, חשב $C'\leftarrow {\mathsf {NEXT}}(\langle M\rangle ,\langle C\rangle )$ כך שבסיום החישוב הסרט השני יכיל את הקידוד של $C'$.
4. חלץ את הפלט מתוך הקונפיגורציה הסופית המקודדת בסרט השני, העתק לסרט הראשון כמחרוזת הפלט וסיים.

הערות:

• אם M לא עוצרת על x, $M_{U}$ לא עוצרת על $(\langle M\rangle ,x)$.
• המכונה האוניברסלית $M_{U}$ היא מ"ט רגילה! יש לה מספר קבוע של מצבים, פונקצית מעבר, וכו'.. למרות זאת היא מצליחה "להריץ" מכונות עם מספר מצבים כלשהו.

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

מכונת טיורינג אוניברסלית

הפרק הבא: מודל לבעיות הכרעה