המכונה המופלאה

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

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

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

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

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

זה הכל.

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

לפני כן, כדאי לתת את הדעת ל”בעיה” טכנית: הקלטים שניתן להעביר למכונת טיורינג אינם בדיוק מספרים טבעיים. אלו הן סדרות סופיות של אפסים ואחדות, כולל הסדרה שאינה מכילה אף תו. חלק מהסדרות מייצגות את אותו מספר (למשל 1 ו-01). במקרים מסויימים קלט “ריק” עשוי לעניין אותנו, ולמקרה כזה אתייחס בתור “הקלט הוא ‘המילה הריקה’” (הבחירה במילה “מילה” נובעת מכך שלפעמים נהוג לדבר על מכונת טיורינג ככלי לזיהוי שפות פורמליות, כאשר “שפה פורמלית” היא קבוצה של סדרות של תווים - מילים. מכיוון שיותר טבעי לחשוב על זיהוי של מספרים טבעיים לא אתעמק בפורמליזם השקול הזה).

אם כן, מבחינה פורמלית, מכונת הטיורינג שלנו מקבלת סדרה של אפסים ואחדות ובודקת האם הספרה הימנית ביותר היא 0. אם כן, היא מקבלת; אחרת, היא דוחה. הסיבה לכך היא שכאשר מספר מיוצג בצורה בינארית, 0 בספרה הימנית ביותר (ה-“Least significant bit”, שכן ההשפעה שלה על גודל המספר היא הזניחה ביותר) גורר זוגיות של המספר, ו-1 גורר אי זוגיות (נסו להבהיר לעצמכם מדוע).

איך תפעל מכונת טיורינג שכזו? אינטואיטיבית, היא תעבור על הקלט משמאל לימין (הרי הראש הקורא מתחיל בנקודה השמאלית ביותר של הקלט). בכל רגע נתון היא תזכור האם התו האחרון שראתה היה 0 או 1. אם הראש הקורא ינסה לקרוא ויגלה שהסרט ריק, המכונה “תבין” שהתו האחרון שראתה היה הספרה הימנית ביותר, ותחליף את המצב שלה בהתאם לתו שהיא זוכרת: אם היא זוכרת 0 היא תעבור למצב מקבל, ואחרת היא תעבור למצב דוחה.

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

\( q_{acc} \) (acc מלשון “Accept”),

\( q_{reg} \) (rej מלשון “Reject”),

\( q_1 \) (מלשון “ראיתי 1 או רק התחלתי לרוץ”)

ו-\( q_0 \) (מלשון “ראיתי 0”).

המכונה תתחיל את ריצה במצב \( q_1 \), וכאן אני לבטח מבלבל אנשים שכבר מכירים את התחום ורגילים לכך שבדרך כלל המצב שמסומן כ-\( q_0 \) הוא המצב ההתחלתי - אני מקווה שמטרתי כאן ברורה.

הנה דוגמה לאחד המעברים שבפונקצית המעברים: \( \delta(q_1,0)=(q_0,0,R) \). כאן הפונקציה אומרת “בהינתן שאתה במצב \( q_1 \) והראש הקורא קרא 0, עבור למצב \( q_0 \), כתוב 0 על הסרט במקום מה שהיה שם (כלומר, אל תשנה את מה שיש על הסרט) והזז את הראש הקורא צעד אחד ימינה”. אני מקווה שלאחר הפרשנות הזו שאר המעברים יהיו ברורים (כאן b מציין “תא ריק בסרט”):

\( \delta(q_1,1)=(q_1,1,R) \)

\( \delta(q_1,b)=(q_{rej},b,R) \)

\( \delta(q_0,0)=(q_0,0,R) \) \( \delta(q_0,1)=(q_1,1,R) \)

\( \delta(q_0,b)=(q_{acc},b,R) \)

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

אז למה מכונת טיורינג היא דבר טוב? דווקא בגלל פשוטתה היחסית. כפי שודאי הבנתם, יש Trade-off ברור בין רמת הפשטות של מרכיבי המכונה ובין המורכבות של כתיבת תוכניות בה, ואותו Trade-off קיים גם בעולם האמיתי של שפות התכנות. מכונת טיורינג קלה בהרבה לתיאור מאשר מחשב אמיתי (שגם בתיאוריו המופשטים ביותר מכיל גם “רגיסטרים”, ו”יחידת עיבוד אריתמטית” ושאר מרעין בישין) ולכן יותר קל להוכיח עליה דברים, וחשוב יותר - לבצע סימולציה שלה באמצעות אובייקטיים מתמטיים אחרים. אביא דוגמה לטענה זו בהמשך, כשאדבר על אי הכריעות של בעיית הריצוף על ידי Wang tiles - בעיה שלדעתי היא מהבעיות המקסימות ביותר שניתנות להצגה מייד כשמתחילים להציג את התחום.

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