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

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

 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