בעיית העצירה

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

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

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

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

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

לרוע המזל, טעויות תכנות עלולות לגרום בקלות לבנייה של תוכנות שלא עוצרות לעולם למרות שציפינו שהן יעצרו. הנה דוגמה נפוצה, משפת האימים ++C. נניח שאנחנו רוצים לכתוב לולאה שתרוץ שוב ושוב כל עוד משתנה כלשהו, notFinished שמו, שווה ל-1. נשמע הגיוני, לא? הנה הלולאה:

while (notNinished=1){

... (doing stuff)

}

מה הבעיה כאן? שהתחביר של ++C לא משתמש בסימן "=" לצורך השוואה, אלא ב-"==". כלומר, מה שאני בודק אינו האם notFinished שווה ל-1. מה שקורה בפועל הוא שבכל איטרציה, המספר 1 מושם בתוך המשתנה notFinished, ומה שה-while בודק הוא את תוצאת ההשמה הזו - 1, שנחשב ל-"true" לוגי. כלומר, הלולאה תמשיך לרוץ לנצח, לא משנה איזה ערך יקבל notFinished בפנים.

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

while (1=notFinished)

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

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

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

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

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

בואו נניח שיש לנו דרך לפתור את בעיית העצירה, ונראה אילו בעיות מתמטיות זה מאפשר לנו לפתור.

• השערת גולדבך: נבנה מכונה שעוברת על כל המספרים הזוגיים הגדולים מ-4. עבור כל מספר כזה נעבור על כל הפירוקים האפשריים שלו לסכום שני מספרים גדולים מ-2 ונבדוק לכל אחד משני המספרים בפירוק אם הם ראשוניים. אם כן, ממשיכים למספר הבא. אם לא, וגמרנו לעבור על כל הפירוקים, עוצרים ומוציאים פלט "השערת גולדבך שגויה". כעת, בודקים האם המכונה שבנינו עוצרת אי פעם או לא. אם היא עוצרת - השערת גולדבך שגויה. אם אינה עוצרת, השערת גולדבך נכונה.
• המשפט האחרון של פרמה (שאמנם, הוכח בינתיים בשיטה קונבנציונלית, ועדיין): בונים מכונה שעוברת בשיטתיות על כל הרביעיות \( (x,y,z,n) \) של מספרים טבעיים עם \( n>2 \) (איך עושים זאת? אתגר לקוראים) ועבור כל רביעייה בודקים האם מתקיים \( x^n+y^n=z^n \). אם כן, עוצרים ומוציאים פלט "המשפט האחרון של פרמה לא נכון". בודקים האם המכונה עוצרת או לא. אם היא עוצרת, המשפט האחרון של פרמה לא נכון. אם היא לא עוצרת, הוא נכון.
• משוואות דיופנטיות: בדומה למשפט האחרון של פרמה, אבל כאן עוברים בשיטתיות על כל ההצבות האפשריות של מספרים שלמים למשתנים של המשוואה.
• האם קיים מספר פרמה ראשוני פרט לחמשת הראשונים: נבנה מכונה שלכל מספר פרמה \( F_n \) עבור \( n>4 \), בודקת האם הוא ראשוני: אם הוא ראשוני, היא עוצרת ומדפיסה "כן". בודקים האם המכונה עוצרת או לא: אם כן, יש עוד ראשוני פרמה; אם לא, אין.

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

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

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

בפעם הבאה - ההוכחה עצמה.