P2(X)

{

A=POLYNDROM(X)

IF (A==!) THEN

       RETURN    

ELSE

     WHILE (1)   

}

הוכחה: 1. נבצע רדוקציה הפוכה מ- H

2. בהינתן זוג (P,W)    נרצה f(P,W)=Q  כך ש- P(W)  עוצרת אם"ם L(Q)   לא רגולרית.

Q צריך להיות  תלוי ב- P ו- W מסוימים.

Q(STRING X)

{

P(W)

A=POLYNDROM(X)

IF (A==1) THEN

    RETURN

WHILE(!)

}

אם P(W) לא עוצרת אז L(Q)=Æ  אם P(W)  עוצרת אז  L(Q) פולנידרום, זאת אומרת L(Q) רגולרית אם"ם P(W)   לא עוצרת. f ניתנת לחישוב.     

                                                                                מ.ש.ל. 

משפט POST

תהי L  שפה אם גם L וגם `L ניתנות לקבלה אז L ניתנת להכרעה. המשפט נכון גם בכיוון ההפוך.

הוכחה: תהי PL תוכנית שמקבלת את L  ותהי`PL   תוכנית שמקבלת את      `Lנבנה תוכנית CHECK_L  שמכריעה L.   CHECK_L(X)  מריצה את PL(X)  ואת `PL(X)  במקביל, בהכרח אחת תעצור. אם PL(X) עצרה אז CHECK_L  תחזיר 1, אם `PL(X)עצרה אז CHECK_L(X)

תחזיר 0.                                             

                          מ.ש.ל.

מסקנה ממשפט POST: `H  לא ניתנת לקבלה.

הוכחה: נניח בשלילה `Hכי H ניתנת לקבלה. H גם ניתנת לקבלה Ü H  ניתנת להכרעה בסתירה. 

                               מ.ש.ל.