1.       לבחור שפה A שהיא לא כריעה. 2.        למצוא רדוקצית מ- A ל- B 3.      לוודא שהרדוקציה ניתנת לחישוב.

דוגמא: עבור תוכנית P נסמן ב – L(P) את אוסף הקלטים שעבורם P עוצרת

תהי B={ (P1,P2) | L(P1) Ç L(P2) ¹Æ }

טענה: B לא ניתנת להכרעה

הוכחה: נעשה רדוקציה מ   Hany שהיא לא ניתנת להכרעה ,

{אוסף תוכניות P ={1* Í å  Hany  ,  (P2,P1)} ={2* Í å B , רוצים f  שמקבלת תוכנית P ומחזירה זוג תוכניות (P1,P2)  כך ש PÎHany אם"ם  (P1,P2) ÎB , כלומר קיים W שעבורו P עוצרת אם"ם קיים U שעבורו גם P1  וגם P2  עוצרות.  נקבע P1=P

P2=P2(U)

{RETURN(1)}

P2 תמיד עוצרת, P1 עוצרת אם P עוצרת ולכן מכיוון ש P לא ניתנת להכרעה  אז גם B לא ניתנת להכרעה. מתקיים ש f ניתנת לחישוב.   מ.ש.ל.

דוגמא: HÆ={P|L(P)= Æ}

טענה: HÆ  לא כריעה.

הוכחה: בשלילה נניח כי HÆ   ניתנת להכרעה , נראה כי Hany  ניתנת להכרעה. כלומר נניח CHECK_ HÆ מכריעה את HÆ נבנה CHECK_Hany  שמכריעה את Hany.

CHECK_Hany(P)

{

A=CHECK_ HÆ(P)

RETURN(!A)}

וזה סתירה לכן  מ.ש.ל.

הגדרה: יהיו   1*A Í å ,   2*B Í å שפות

רדוקצית התאמה הפוכה מ A ל B הינה הפונקציה: 2* å ® 1* å f:  כך שלכל 1*,  XÎå                   f(X) ÏB  Û    XÎ A.

מתקיים אם B כריעה וקיימת רדוקצית התאמה הפוכה מ A לB ניתנת לחישוב אז גם A ניתנת להכרעה.

נגדיר את השפה R:     P } תוכנית ומתקיים L(P)  רגולרית R = {P |

[L(P) הוא אוסף הקלטים עליהם P עוצרת, R לא רגולרית אלא השפה של התוכנית רגולרית]

טענה: R לא כריעה.

  אורך המילה גדול מ –4     L(P)={W|  |W| ³ 4}

PÎR

P(STRING X)

{

IF ( |X| ³4 ) THEN
   RETURN 0

ELSE

  WHILE (1)

}

נניח כי קיימת הפרוצדורה POLYNDROM כך שבהינתן קלט X אם הוא פולינדרום מחזירה 1,

אחרת מחזירה 0.   [שפת הפולינדרומים אינה רגולרית].