» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
בעיית העצירה
דף ראשי  רדוקציות  בעיית העצירה גרסה להדפסה

בעיית העצירה 

 

ננסה לפתור את השאלות הכלליות:

אימות תוכנית

נרצה להסתכל על הקוד של התוכנית – בלי שנריץ אותה – ולקבוע האם התוכנית

עושה מה שהיא צריכה לעשות

בעיית העצירה

בהינתן תוכנית   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 ()

{       

 

 09-02-04 / 10:04  עודכן ,  01-01-04 / 13:32  נוצר ע"י שמרית דויטש  בתאריך 
 מבוא לרדוקציות - הקודםהבא - בעיית העצירה-2 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 4