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

בעיית העצירה- המשך

נגדיר שפה נוספת:

 P }  תוכנית, וקיים קלט W  ,כך ש - P עוצרת עלW    Hany = {P | 

      P(X)

     {

       WHILE(1)

     }

 

      P(X)

   }      

       IF (X=="ABC") THEN

           RETURN (1)

       ELSE  

           WHILE (1)

{       

טענה:  Hany  לא ניתנת להכרעה. נראה כי H כריעה בסתירה לכך שהוכחנו שהיא לא כריעה.

 כלומר בשלילה נניח קיום פרוצדורה CHECK_Hany  שמכריעה את Hany נבנה בעזרתה פרוצדורה CHECH_H שמכריעה את H.

      CHECK_H(P,W)                

}      

        PROGRAM PW;

        PW= COMBINE(P,W)

        RETURN (CHECK_Hany(PW))  

{      

PW מריצה את P על W.

       CHECK_Hany(Q)

}       

           .

           .

           .

{       

 

        COMBINE(X,Y)

}       

         PROGRAM Z

         Z.CODE= “Z(U){“ + X.NAME + “(“ +Y+ “)   RETURN(1) }” + X.CODE

         Z.NAME= “Z”

         RETURN (Z)

{       

 

 COMBINE יוצרת תוכנית Z שמריצה את X  על קלט Y למשל:

        X=JUNK(Y)

}       

          PRINT ("Hello")

{          Y="123”

 

Þ

 

         Z(U)

}        

          JUNK(123)

           RETURN(1)

{        

 

       JUNK(Y)

                              PRINT("hello");}           

 COMBINE(P,W) מייצרת תוכנית PW שמתעלמת מהקלט שלה U ומריצה את P על W

מתקיים:

אם  Pעוצרת על W אז PW עוצרת לכל קלט U – מכיוון שהיא מתעלמת ממנו.

ואם P לא עוצרת על W אז PW לא עוצרת לכל קלט.

Ü H Î(P,W) Û  PW Î Hany   Ü  התוכנית CHECK_H שבנינו אכן מכריעה את H

מ.ש.ל. בסתירה ð

הטעות היא ב – .CHECK _Hany

 

 

 27-01-04 / 10:39  עודכן ,  11-01-04 / 11:36  נוצר ע"י שמרית דויטש  בתאריך 
 בעיית העצירה - הקודםהבא - הגדרה פורמלית 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 5