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

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

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

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

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

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

זה הכל.

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

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

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

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

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

$latex q_{acc}$ (acc מלשון "Accept"),

$latex q_{reg}$ (rej מלשון "Reject"),

$latex q_1$ (מלשון "ראיתי 1 או רק התחלתי לרוץ")

ו-$latex q_0$ (מלשון "ראיתי 0").

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

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

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

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

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

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

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

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

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

20 תגובות בנושא “המכונה המופלאה”

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

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

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

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

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

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

  5. (בדר"כ מרעין בישין, לא מריעין. מריעין הוא פועל או שם פעולה, לעומת מרעין שהוא שם עצם.)

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

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

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

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

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

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *