שאלות חזרה- המשך    קבע האם השפה:  {קיים קבוע Cp כך ש- P עוצרת על כל קלט תוך לא יותר  מ-Cp צעדים | P}= Hboun ניתנת להכרעה?   פתרון: טענה: Hbound  איננה ניתנת להכרעה. הוכחה: ברדוקציה מ-H. *Σ1={(P,w)|P is a program, w is a string} > H *Σ2= {Q| Q is a program} > Hbound   נבנה רדוקציה f:Σ1*→Σ2* , כך שבהינתן זוג (P,w)  מוציאה f(P,w)=Q, כך ש- (P,w) שייכת ל-H אמ"ם Q  שייכת ל-Hbound.             Q(x)               {                P(w);                 Return;               } מתקיים: אם P(w) עוצרת, אזי יהי d מספר הצעדים של P(w) עד לעצירה. אזי לכל קלט x , Q(x) מבצעת d צעדים. כלומר Q שייכת ל- Hbound. (עבור Cp=d) אם P(w) לא עוצרת, אזי לכל קלט x, Q מבצעת אינסוף צעדים. בפרט אין קבוע Cp כנדרש. כלומר Q לא שייכת ל- Hbound.   האם השפה: { p1 עוצרת על p2 אמ"ם p2 עוצרת על p1| (p1,p2)}=L4 ניתנת לקבלה?   פתרון: טענה: L4 לא ניתנת לקבלה. הוכחה: רוצים p(w) לא עוצרת אמ"ם (p1,p2) שייך ל- L4.                P1(x)                {                    p(w);                 }                  p2(x)                {                   while(1);                 } p2 לא עוצרת על אף קלט, ובפרט גם לא על p1. P1 לא עוצרת על אף קלט אם p(w) לא עוצרת. אם p(w) עוצרת, אזי p1 עוצרת על כל קלט, בפרט על p2. אבל p2 לא עוצרת על אף קלט, לכן (p1,p2) לא שייך ל- L4.