תורת החישוביות/שקילות מודלי חישוב

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

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

הגדרה: שני מודלים יקראו שקולים אם כל פונקציה $f$ (חלקית או מלאה), הניתנת לחישוב במודל אחד, ניתנת לחישוב במודל השני.

על מנת להוכיח שקילות, נראה כיצד ניתן "לסמלץ" כל מכונה במודל חישוב אחד, על-ידי מכונה מתאימה במודל החישוב השני.

שקילות מכונת טיורינג "חסרת מנוחה" למ"ט הסטנדרטית

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

על מנת להראות שקילות יש להוכיח שני כיוונים.

• כיוון א' - סימלוץ מכונה "חסרת מנוחה" על-ידי מ"ט רגילה. כיוון זה פשוט, מכיוון שכל מ"ט חסרת מנוחה הינה למעשה מ"ט רגילה שלא עושה שימוש בהשארת הראש במקומו (הכיוון S). לכן, בהינתן מכונה "חסרת מנוחה", העתקת כלל הפרמטרים (המצבים, פונקציית המעברים וכו'), תתן לנו מ"ט במודל הרגיל המתנהגת באופן זהה.
• כיוון ב' - סימלוץ מ"ט רגילה $M$ על-ידי מכונה חסרת מנוחה $R$. הרעיון הוא כדלקמן: המכונה $R$ תתנהג בדיוק כמו $M$ פרט לכך שבכל פעם שהמכונה $M$ תבצע מעבר בו הראש נשאר במקום, המכונה "חסרת המנוחה" $R$ תזיז את הראש צעד ימינה ואז מייד צעד שמאלה חזרה ותמשיך בחישוב כמו $M$. באופן פורמלי, לכל מעבר $\delta (q,x)=(p,y,S)$ ב-$M$ נגדיר ב-$R$ את המעבר: $\delta (q,x)=(p',y,R)$ ואת המעברים $\delta (p',\sigma )=(p,\sigma ,L)$ לכל $\sigma \in \Gamma$. המעבר הראשון משנה את הסרט בהתאם להתנהגות M, ואז מזיז את הראש צעד אחד ימינה, כאשר הוא עובר למצב מיוחד $p'$ שלמעשה "זוכר" שאנחנו צריכים לזוז ימינה ולעבור למצב $p$ (כי במקור, M עברה למצב p). המעבר השני "מתעלם" ממה שרשום על הסרט, מזיז את הראש חזרה צעד שמאלה, ועובר למצב שזכרנו, p.

תרגיל : הסבר מדוע הפתרון בו זזים שמאלה ולאחריו צעד ימינה אינו תקין
רמז: מה קורה כאשר הראש נמצא בקצה?

שקילות מ"ט מרובת סרטים

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

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

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

טענה: לכל $k\geq 2$ מכונת טיורינג בעלת k סרטים שקולה למודל הסטנדרטי עם סרט זכרון יחיד.

הכיוון הישיר הינו פשוט - כל מכונה עם k סרטים יכולה לסמלץ מכונה בעלת סרט יחיד על-ידי "התעלמות" משאר הסרטים.

הוכחת הכיוון השני מתבצעת לפי הרעיון הבא, כאשר לשם פשטות נניח כי $k=2$‏. בהנתן מכונה עם שני סרטים M, נבנה מכונה $M^{*}$ בעלת סרט יחיד אשר תבצע סימולציה של הרצת שני הסרטים על גבי סרט יחיד. לשם כך, נצטרך אלפבית עבודה גדול במיוחד אשר בו כל אות מסמלת את שני התווים שנמצאים על הסרט של המכונה M. למשל, נניח שבמכונה הדו-סרטית הסרט הראשון מכיל abc והשני 01 (ושאר התאים ריקים), אזי הסרט של $M^{*}$ יכיל $(a,0)(b,1)(c,\sqcup )$ כאשר כל זוג בתוך סוגריים מהווה "אות יחידה" באלפבית של $M^{*}$. בעיה נוספת עמה יש להתמודד, היא שב-M יש שני ראשים שיכולים להיות בשני מקומות שונים.. פתרון לכך מתבצע על-ידי "סימון" מיקום הראשים במכונה הדו-סרטית, על-ידי הוספת תג. למשל, אם בדוגמא לעיל הראש הראשון נמצא בתא הראשון (על ה"a"), והראש השני נמצא בתא השלישי, הריק, אזי במכונה $M^{*}$ תוכן הסרט יהיה $(a',0)(b,1)(c,\sqcup ')$. לסיכום, אם $\Gamma$ הוא האלפבית של M אזי האלפבית של $M^{*}$ נתון על-ידי

$\Gamma ^{*}=\Gamma \cup [(\Gamma \cup \Gamma ')\times (\Gamma \cup \Gamma ')]$

כאשר $\Gamma '=\{a'\mid a\in \Gamma \}$.

הסימולציה מתבצעת באופן הבא.

1. תחילת חישוב: המרת הקלט לצורת ה"זוגות" עד שמגיעים לתא ריק, וסימון ה"תגים" על האות הראשונה בשני הסרטים.
2. צעד חישוב
   1. מבצעים סריקה לימין עד ש"מוצאים" את שני התגים. כל תג שמצאנו מעביר אותנו למצב בקרה ש"זוכר" את האות שראינו.
      דוגמא: נניח שבתחילה אנו במצב $q$, והסרט מכיל $(a',0)(b,1)(c,\sqcup ')$. אנו מתחילים בסריקה ימינה, וראשית נמצא את מיקומו של הראש הראשון מביט על האות a. בשל כך נעבור למצב $q^{a,?}$ המסמל שהראש הראשון רואה a ואת הראש השני עדיין לא מצאנו. נמשיך בסריקה עד מציאת התג השני שיגרום לנו לעבור למצב $q^{a,\sqcup }$.
   2. לפי שתי האותיות שקראנו נעבור למצב המתאים ש-M הייתה עוברת, ונזכור כיצד יש לשנות את הסרט. נניח כי המעבר של M הוא $\delta (q,x,y)=(p,t,u,d_{1},d_{2})$. אזי אם $M^{*}$ היתה במצב $q^{x,y}$ היא תעבור למצב $p^{t-d_{1},u-d_{2}}$ המסמל שיש לשנות את האות מתחת לראש הראשון ל-t ולהזיז את הראש לכיוון $d_{1}$, וכן לשנות את האות מתחת לראש השני ל-u ולהזיז את הראש השני בהתאם ל-$d_{2}$.
   3. נסרוק את הסרט שמאלה עד שנתקל בתג. נבצע את השינוי המתאים של האות, ונזיז את ה"תג" בהתאם לדרוש, ונעבור למצב המסמן שסיימנו פעולה זו.
      לפי הדוגמא לעיל, לאחר שמצאנו, נניח, את הראש השני, נעבור למצב $p^{t-d_{1},\surd }$, ונמשיך בסריקה עד שנמצא את הראש הראשון, נבצע את כתיבת האות והזזת התג, ונעבור למצב $p^{\surd ,\surd }$
   4. נעבור למצב $p^{?,?}$ ונתחיל צעד חישוב חדש.
3. כאשר $M$ עוברת למצב סופי, נסרוק שוב את הסרט ונתרגם חזרה את "זוגות" האותיות לאותיות רגילות (נמחק את כל תוכן כל הסרטים פרט לתוכן סרט הראשון), נזיז את הראש למקום בו מונח הראש הראשון של-M ונעבור ב-$M^{*}$ למצב סופי.

דוגמה למכונה לא-שקולה למ"ט

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

דוגמה: נביט בפונקציה $f(x_{1}\cdots x_{n})=x_{n}$ אשר עבור כל קלט $x_{1}\cdots x_{n}$ מחשבת כפלט את הסיבית האחרונה של הקלט. קל לראות שניתן לחשב את הפונקציה במכונת טיורינג רגילה.

כעת נראה באופן פורמלי כי לא ניתן לעשות כן במכונה "מתקדמת בלבד". נניח בשלילה כי מכונה "מתקדמת בלבד" $M$ מסוגלת לחשב את הפונקציה $\ f$. נביט בריצת המכונה עבור הקלט "000", מכיוון שהמכונה אינה יכולה להזיז את הראש שמאלה, כאשר הראש זז לתא השני, האות הרשומה בתא הראשון חייבת להיות 0 (אחרת פלט המכונה עבור הקלט "000" יהיה שגוי). עתה, נביט בחישוב עבור הקלט "001". ריצת המכונה על קלט זה עד הרגע בו הראש זז לתא השני חייבת להיות זהה לריצת המכונה על הקלט "000", מכיוון שהראש רואה את "אותו הדבר" (כלומר, בשני המקרים הראש "רואה" את הסימן 0, במצב הבקרה $q_{0}$, ולכן שני המקרים יתנהגו באופן זהה, לפחות עד שהראש יגיע לתא השלישי). מכאן, שכאשר הראש זז לתא השני, בתא הראשון יהיה כתוב "0". מכיוון שהראש לא יכול לזוז יותר שמאלה, הערך חייב להשאר 0 עד סיום ריצת המכונה, אבל זו סתירה, מכיוון שהפלט המתאים הינו "1" (נזכיר כי הפלט מוגדר בתור המחרוזת שנמצאת משמאל לראש בעת סיום הריצה).

התזה של צ'רץ'-טיורינג

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

	כל מודל סביר וכללי של מכונת חישוב שקול למודל מ"ט

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

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

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

הפרק הקודם: מכונת טיורינג

שקילות מודלי חישוב תרגילים

הפרק הבא: מכונת טיורינג אוניברסלית