דוגמא: HÆ ={P|L(P)= Æ} לא ניתנת להכרעה.

טענה: HÆ לא ניתנת לקבלה.

הוכחה: }             קיים W שעבורו P(W)  עוצרת HÆ={P| Hany  =`

נבנה תוכנית ACCEPT_Hany(X)  שמקבלת את Hany כלומר בהינתן P, ACCEPT_Hany(P) עוצרת אם"ם PÎHany

ACCEPT_Hany(P)

}

CHOOSE W NON-DETRMINISTICALLY

P(W)

RETURN()

{

אם PÎHany אז קיים חישוב של ACCEPT_Hany(Wo) שעוצר החישוב שמוצא W=Wo. לעומת זאת אם  PÏHanyאז כל חישוב של ACCEPT_Hany(P) לא עוצר. כלומר השפה של ACCEPT_Hany היא בדיוק Hany כלומר Hany ניתנת לקבלה Ü HÆ לא ניתנת לקבלה

מ.ש.ל.

דוגמא: {ב- L(P) יש מילים באורך זוגי בלבדHeven ={P| 

טענה: Heven לא ניתנת לקבלה .

הוכחה: Heven  לא ניתנת להכרעה, נראה כי `Heven ניתנת לקבלה. נבנה תוכנית ACCEPT_`Heven  שמקבלת את `Heven.   {ב L(P) קיים X באורך אי זוגי `Heven= { P |

ACCEPT_`Heven(P)

}

GUESS X SUCH THAT |X| ODD

P(X)

RETURN

{

אם PÎ`Heven     אז קיים Xo  כך ש P(Xo) עוצרת Xo באורך אי זוגי Ü קיים חישוב של ACCEPT_`Heven(P) שעוצר – החישוב שמוצא X=Xo לעומת זאת אם PÏ`Heven אז לכל X באורך אי זוגי P(X) לא עוצרת ולכן לא קיים חישוב של  ACCEPT_`Heven(P) שעוצר.

Ü ACCEPT_`Heven מקבלת את `Heven Ü Heven  לא ניתנת לקבלה

מ.ש.ל.                

יש שפות שלא הם ולא המשלים שלהן ניתנות לקבלה, בניגוד לשפות שראינו עד עכשיו שהם לא ניתנות לקבלה אבל השפה המשלימה ניתנת לקבלה.

דוגמא: B={(P1,P2)|  L(P1) Í L(P2)}

טענה: B לא ניתנת לקבלה.

הוכחה: נניח ש- B ניתנת לקבלה נראה כי HÆ ניתנת לקבלה. כלומר בשלילה נניח כי קיימת ACCEPT_B  שמקבלת את B נבנה HÆ  ACCEPT_ שמקבלת את HÆ.

HÆ(P) ACCEPT_ עוצרת אם"ם Î HÆ P.

נתון ACCEPT_B(P1,P2) עוצרת אם"ם   L(P1) Í L(P2)

f(P)

}

P1=P

P2=NO_STOP(X)

}

   WHILE(1)

}

RETURN(P1,P2)

{

HÆ(P) ACCEPT_

}

(P1,P2)=f(P)

ACCEPT_B(P1,P2)

RETURN

{

ACCEPT_B(P1,P2)

}

.

.

.

{

אז אם Î HÆ P אזי L(P) Í L(NO_STOP) Ü  (P,NO_STOP)ÎB Ü ACCEPT_B(P, NO_STOP) תעצור Ü HÆ(P) ACCEPT_ תעצור.

אם Ï HÆ P אז L(P) Ë L(NO_STOP) Ü  (P,NO_STOP)ÏB Ü ACCEPT_B(P, NO_STOP) לא תעצור Ü HÆ(P) ACCEPT_ עוצרת אם"ם Î HÆ P

                                                                       מ.ש.ל.

HÆ(P) ACCEPT_ מקבלת את HÆ בסתירה Ü ACCEPT_B  לא קיימת.           מ.ש.ל.