בעיית העצירה (אני מסרב לתת כאן שם מתחכם)

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

אלא שבשום מקום לא נדרש שהמכונה אכן תעצור. קל מאוד לכתוב מכונה שאינה עוצרת. הנה: מכונה בעלת מצב אחד, $latex q_0$, ובעלת פונקצית המעברים הבאה: $latex \delta(q_0,0)=\delta(q_0,1)=\delta(q_0,\flat)=(q_0,0,R)$ (ה-$latex \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 ונבדוק לכל אחד משני המספרים בפירוק אם הם ראשוניים. אם כן, ממשיכים למספר הבא. אם לא, וגמרנו לעבור על כל הפירוקים, עוצרים ומוציאים פלט "השערת גולדבך שגויה". כעת, בודקים האם המכונה שבנינו עוצרת אי פעם או לא. אם היא עוצרת – השערת גולדבך שגויה. אם אינה עוצרת, השערת גולדבך נכונה.
  • המשפט האחרון של פרמה (שאמנם, הוכח בינתיים בשיטה קונבנציונלית, ועדיין): בונים מכונה שעוברת בשיטתיות על כל הרביעיות $latex (x,y,z,n)$ של מספרים טבעיים עם $latex n>2$ (איך עושים זאת? אתגר לקוראים) ועבור כל רביעייה בודקים האם מתקיים $latex x^n+y^n=z^n$. אם כן, עוצרים ומוציאים פלט "המשפט האחרון של פרמה לא נכון". בודקים האם המכונה עוצרת או לא. אם היא עוצרת, המשפט האחרון של פרמה לא נכון. אם היא לא עוצרת, הוא נכון.
  • משוואות דיופנטיות: בדומה למשפט האחרון של פרמה, אבל כאן עוברים בשיטתיות על כל ההצבות האפשריות של מספרים שלמים למשתנים של המשוואה.
  • האם קיים מספר פרמה ראשוני פרט לחמשת הראשונים: נבנה מכונה שלכל מספר פרמה $latex F_n$ עבור $latex 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. תרגיל לא מסובך במיוחד שעוזר לוודא שההגדרות מובנות הוא להוכיח זאת.

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

 

 

16 תגובות בנושא “בעיית העצירה (אני מסרב לתת כאן שם מתחכם)”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

כתיבת תגובה

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