בעיית העצירה
ננסה לפתור את השאלות הכלליות:
אימות תוכנית
נרצה להסתכל על הקוד של התוכנית – בלי שנריץ אותה – ולקבוע האם התוכנית
עושה מה שהיא צריכה לעשות
בעיית העצירה
בהינתן תוכנית P וקלט W האם התוכנית P (אם היינו מריצים אותה) הייתה עוצרת על הקלט W ?
נסמן ב – H את השפה הבאה:
P } תוכנית, W קלט ,ו - P עוצרת עלW H={(P,W) |
משפט: Hלא ניתנת להכרעה – לא כריעה.
הוכחה: (בשלילה) נניח כי H ניתנת להכרעה. תהי CHECK_H(P,W) תוכנית שמכריעה את H, זאת אומרת שאם H עוצרת על W אז היא מחזירה 1 ואם לא אז היא מחזירה 0.
נבנה תוכנית אחרת STUPID :
STUPID(Q)
}
A=CHECK_H(Q,Q)
IF (A==1) THEN
WHILE (1)
ELSE
RETURN(1)
Q היא מחרוזת ולכן אפשר להתייחס אליה כאל תוכנית.
STUPID מכילה גם את הקוד של CHECK_H
מה קורה כאשר Q הינו הקוד של STUPID ? כלומר האם STUPID עוצרת על STUPID ?
ישנן 2 אפשרויות:
1. כן , כלומר STUPID עוצרת על STUPID Ü (STUPID,STUPID) H Î Ü CHECK_H(STUPID,STUPID) אמורה להחזיר 1 Ü STUPID(STUPID) לא עוצרת . סתירה.
2. לא, כלומר STUPID(STUPID) לא עוצרת Ü (STUPID,STUPID) H Ï Ü CHECK_H(STUPID,STUPID)=0 Ü STUPID(STUPID) עוצרת. סתירה.
כיוון ששתי האפשרויות נכשלו אפשר להסיק שהייתה טעות בהנחה בדרך, ההנחה היחידה שהנחנו היא שקיימת תוכנית CHECK_H
מסקנה: CHECK_H לא קיימת כלומר H לא ניתנת להכרעה. ð
טענה: H ניתנת לקבלה.
הוכחה: נראה שקיימת תוכנית U שבהינתן (P,W) , U(P,W) עוצרת Û H Î(P,W)
כלומר Û P עוצרת על W. U מריצה את P על W:
U(P,W)
}
P(W)
RETURN ()