שאלות חזרה   נניח שקיים סרט קלט המייצג את המערך In[ ]  , מערך אינסופי. התוכנית הבאה מחשבת את מספר האיברים השונים מ- # במערך :               1)Sum=0              2)X=1              3)If In[X]==0 goto 7              4)Sum=Sum+1              5)X=X+1              6)goto 3              7)end כתבו את טבלת המעברים השקולה לפרוצדורה הנ"ל.   פתרון: S(#,#)            q1(L,R) q1(1, #)         q1(L, #) q1(#,#)          q1(L, #) q1($,#)         q2(R, #) q2(1, #)         q3(1,1) q3(1,1)         q3(R,R) q3(1, #)        q3(R, #) q3(#,#)         q2(R, #) q2(#,#)           q4(L,L) q4(1,1)           q4(#,1) q4(#,1)          q4(L,1) q4($,1)         q5(1, #) q4($,#)            h(#,#) q5(1, #)        q6(R,L) q6(#,1)        q5(1, #) q6(#,#)          h(#,R)   קבע האם השפה: {ב- L(P) יש מילים מאורך זוגי בלבד | P }= Heven ניתנת להכרעה:   פתרון: טענה: Heven אינה ניתנת להכרעה. הוכחה: ברדוקציה הפוכה מ-H . *Σ1={(P,w)|P is a program, w is a string} > H *Σ2= {Q| Q is a program} > Heven נבנה רדוקציה f:Σ1*→Σ2* , כך שבהינתן זוג (P,w)  מוציאה f(P,w)=Q, כך ש- (P,w) שייכת ל-H אמ"ם Q לא שייכת ל-Heven.             Q(x)             {                P(w);                 Return;              } מתקיים:  אם P(w) עוצרת אזי Q עוצרת לכל קלט, בפרט גם לקלטים באורך אי-זוגי, כלומר Q לא שייכת ל- Heven. אם P(w) לא עוצרת, אזי Q לא עוצרת לכל קלט. בפרט, כל הקלטים שעבורם Q עוצרת הינם באורך אי זוגי, כלומר Q שייכת ל-Heven. כלומר (P,w) שייכת ל-H אמ"ם Q לא שייכת ל- Heven.