בעיית העצירה

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

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

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

לעומת זאת ניתן לבנות מכונת טיורינג שמקבלת כל תוכנית מחשב $Q$ וקלט $X$ כך שתוכנית המחשב עוצרת על קלט זה, ולא מקבלת אך אולי גם לא דוחה אם התוכנית אינה עוצרת על קלט זה, ולכן בעיית העצירה ניתנת למנייה רקורסיבית ושייכת לקבוצה $RE/R$.

הוכחת אי-כריעות

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

נניח שיש אלגוריתם $Halt(Q,X)$ שמקבל אם $Q$ עוצרת על $X$ ודוחה אחרת, ונתבונן בתוכנית $A(Q)$ הבאה המקבלת תוכנית $Q$ כקלט:

אם $Halt(Q,Q)$, הכנס ללולאה אינסופית.

אחרת, עצור.

נשים לב כי מעבירים כאן את $Q$ פעמיים: הן בתור התוכנית שיש לבדוק והן בתור הקלט לתוכנית שעליו היא נבדקת. אין בעיה עקרונית בהעברת $Q$ כקלט - ניתן לחשוב על כל קלט כרצף של תווים, ולכן גם תוכנית מחשב יכולה להיחשב לקלט.

נשאל עכשיו, האם תעצור $A$ עבור הקלט $A$? (כלומר, במקרה שהתוכנית $A$ תקבל את עצמה) נחלק לשני מקרים, ונקבל סתירה בשניהם:

נניח ש-$\ A(A)$ תעצור. מכיוון שעל פי הצורה שבה הגדרנו את $A(A)$, היא עוצרת רק אם לא מתקיים $Halt(A,A)$, נסיק כי כך הם פני הדברים. אולם, מכיוון שמהגדרת האלגוריתם $Halt$ הוא אינו מתקיים רק אם $A$ אינה עוצרת על עצמה נגיע לסתירה - הנחנו ש-$A(A)$ עוצרת וקיבלנו שהיא בהכרח אינה עוצרת.

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

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

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

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

שייכות בעיית העצירה ל $RE$

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

ניתן לבנות מכונת טיורינג שמריצה את תוכנית $Q$ על $X$ וכשהיא עוצרת לקבל. אם $Q$ עוצרת על $X$ המכונה תזהה זאת ותקבל, אחרת היא רצה בלי לעצור.

בעיית העצירה בתוכנית עם זיכרון סופי

כשמדובר במחשב בעל זיכרון סופי - כל תוכנית מחשב שרצה על מחשב זה תעצור בזמן שהוא לכל היותר 2 בחזקת מספר הביטים בזיכרון המחשב של צעדים, או תיכנס ללולאה אינסופית. מספר צעדים זה הוא אקספוננציאלי, אבל סופי. לכן ניתן לפתור את בעיית העצירה על מחשב בעל זיכרון סופי. (לדוגמה: אם זיכרון המחשב הוא 8 סיביות (בית אחד), כל תוכנית מחשב תעצור לכל היותר אחרי 256 צעדים, או תיכנס ללולאה אינסופית. אם זיכרון המחשב הוא 1 KB‏ (8192 ביטים או 1024 בתים), כל תוכנית מחשב תעצור לכל היותר אחרי 2⁸¹⁹² צעדים, או תיכנס ללולאה אינסופית). בזיכרון המחשב יש לכלול גם את זיכרון המעבד, כגון אוגרים וכו', וכן את תוכנית המחשב עצמה. כמו כן לא ניתן עקרונית לממש זיכרון אינסופי, ולו בגלל הצורך בחומר לשם זיכרון וכמות החומר ביקום סופית.

ראו גם

• לכסון

לקריאה נוספת

• M. Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997
• J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., 1979

קישורים חיצוניים

• הוכחה בחרוזים לאי הכריעות של בעיית העצירה
• גדי אלכסנדרוביץ', בעיית העצירה, באתר "לא מדויק", 26 בספטמבר 2007
• סרטון אנימציה המסביר את בעיית העצירה וההוכחה, Proof That Computers Can't Do Everything (The Halting Problem), סרטון באתר יוטיוב (קיים גם תרגום לעברית)
• וידאו של הרצאה שמסבירה את הבעיה ואת ההוכחה ללא נוסחאות ובלי להניח שם רקע מתמטי, סרטון באתר יוטיוב
• שמואל וינוגרד, ‏מכונת טיורינג, מחשבות 35, יולי 1972, עמ' 13–17
• וידאו של הוכחת הטענה בעברית, סרטון באתר יוטיוב, סרטון ביוטיוב (החל מ-1:10:00 בערך)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

33093320בעיית העצירה