בעיית העצירה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

הוכחת אי-כריעות[עריכת קוד מקור | עריכה]

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]