עוד מכונות מופלאות

הרחבות של המודל

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

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

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

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

טכניקה חביבה לסמלץ מכונה בת n סרטים באמצעות מכונה בת סרט אחד היא “לחבר” את כל הסרטים יחד במעין ריצ’רץ’: התא הראשון בסרט של המכונה הפשוטה יהיה התא הראשון של סרט מס’ 1 במכונה המורכבת, התא השני יהיה התא הראשון של סרט מס’ 2 וכן הלאה. התא ה-n+1-י יהיה התא השני של סרט מ’ 1 במכונה המורכבת, וכן הלאה וכן הלאה. שוב, באמצעות מצבי זכרון מתאימים (“עד עכשיו קראתי את תוכן סרטים מס’ 1, 2, ו-3: התוכן היה 0, 0, ו-1, בהתאמה”) ניתן לבצע סימולציה של המכונה המורכבת.

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

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

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

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

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

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

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

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

…ועכשיו למשהו שונה לגמרי.

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

צריך לתאר את כל המצבים הפנימיים שלה. דרשנו במפורש שיהיה מספר סופי מהם, כך שזה בסדר.

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

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

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

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

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

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

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

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