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

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

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

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

• $Q=\{1,2,3,\dots \}$ כאשר המצב ההתחלתי $q_0=1$.
• $F=\{2,3\}$ שכן לא נדרשים יותר משני מצבים סופיים (אחד לקבלה, אחד לדחייה)
• $\mathrm{\Sigma }=\{1,2,3,\dots ,|\mathrm{\Sigma }|\}$
• $\mathrm{\Gamma }=\{1,2,3,\dots ,|\mathrm{\Gamma }|\}$
• $\bigsqcup =|\mathrm{\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,\mathrm{\Gamma },\mathrm{\Sigma },\bigsqcup ,\delta )$ נתון על-ידי:

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

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

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

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

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

סימון

תבנית:מבנה תבנית

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

כעת נראה כיצד ניתן לקודד למחרוזת בינארית [[../מכונת טיורינג#קונפיגורציה|קונפיגורציות]]. כזכור, קונפיגורציה היא אוסף המידע המגדיר את מצב המכונה M בתחילת צעד חישוב. ראינו ב[[../מכונת טיורינג#קונפיגורציה|פרק קודם]] שקונפיגורציה מכילה כמות מידע סופית ועל כן ניתן לקודד אותה למחרוזת בינארית (באורך סופי). הקונפיגורציה $C=(a_1{a}_2\dots a_k,q,i)$ תקודד באופן הבא

$⟨C⟩=1^{a_1}01^{a_2}0\dots 1^{a_{i-1}}\underset{\text{head}}{\underbrace{001^q}}01^{a_i}01^{a_{i+1}}\dots 01^{a_k}$

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

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

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

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

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

• ייתכן שהקידוד $⟨C⟩$ אינו חוקי
• ייתכן ש$⟨C⟩$ אינו מתאים למכונה M (למשל, משתמש באות שאינה ב[[../מכונת טיורינג#הגדרה|אלפבית]] של M)
• ייתכן שC היא קונפיגורציה סופית, ואין לה קונפיגורציה עוקבת.

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

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

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

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

תבנית:טענה תבנית:חלון מידע הוכחה: נניח מכונה בעלת שני סרטים, ונתאר את פעולה על הקלט $(⟨M⟩,x)$:

1. אם $⟨M⟩$ אינו קידוד תקין - עצור מייד עם הפלט $\epsilon$.
2. אחרת - כתוב על הסרט השני את הקונפיגורציה ההתחלתית של M על x.
3. בצע בלולאה:
   כל עוד הקונפיגורציה C המקודדת בסרט השני אינה סופית, חשב $C^{\prime }\leftarrow 𝖭𝖤𝖷𝖳(⟨M⟩,⟨C⟩)$ כך שבסיום החישוב הסרט השני יכיל את הקידוד של $C^{\prime }$.
4. חלץ את הפלט מתוך הקונפיגורציה הסופית המקודדת בסרט השני, העתק לסרט הראשון כמחרוזת הפלט וסיים.

הערות:

• אם M לא עוצרת על x, $M_U$ לא עוצרת על $(⟨M⟩,x)$.
• המכונה האוניברסלית $M_U$ היא מ"ט רגילה! יש לה מספר קבוע של מצבים, פונקצית מעבר, וכו'.. למרות זאת היא מצליחה "להריץ" מכונות עם מספר מצבים כלשהו.

תבנית:תורת החישוביות