1. נניח בשלילה שקיים מבחין כזה' DD ונתאר מ"ט, MM, שמקבלת את LEQ\overline{L_{EQ}}.

MM על קלט M1,M2\langle M_1 \rangle, \langle M_2 \rangle:

  • מריצה את DD על M1,M2\langle M_1 \rangle, \langle M_2 \rangle ומקבלת אמ"מ DD עצר.

קל לראות ש-MM אכן מקבלת את LEQ\overline{L_{EQ}}, מכיוון שלא קיימת מ"ט שמקבלת את LEQ\overline{L_{EQ}} אז לא קיים מבחין כנדרש.

2. נתאר מבחין, DD על קלט (M1,M2)(\langle M_1 \rangle, \langle M_2 \rangle):

  • מריץ את M1M_1 ו-M2M_2 על כל xx לפי סדר לקסיקוגרפי
  • פולט xx אם אחת המכונות קיבלה והשנייה דחתה

נשים לב שמכיוון שמובטח לנו שב-CC רק מכונות שעוצרות אז אם קיים xx כנדרש נמצא אותו בשלב מסוים ואם לא קיים כזה אז DD לא יעצור כנדרש.

Feedback