Question

classification_r_re

עבור מ"ט M1M_1 ו-M2M_2 נסמן fM1(x)=fM2(x)f_{M_1}(x) = f_{M_2}(x) אם שתי המכונות עוצרות בריצה על xx והפלט שלהן זהה. עבור כל אחת מהשפות הבאות קבעו האם היא ב- R, והאם היא ב-RE.

  • }\}לכל MM' ו-xx, fM(M,x)=1f_M(\langle M' \rangle, x) = 1 אם MM' עוצרת על xx ו-0 אחרת L1={M:L_1 = \{\langle M \rangle :
  • L2={(M1,M2):x,fM1(x)=fM2(x)}L_2 = \{(\langle M_1 \rangle, \langle M_2 \rangle) : \forall x, \: f_{M_1}(x) = f_{M_2}(x)\}
  • L3={(M1,M2):x,fM1(x)=fM2(x)}L_3 = \{(\langle M_1 \rangle, \langle M_2 \rangle) : \exists x, \: f_{M_1}(x) = f_{M_2}(x)\}
1

Answers

1. נראה ש-L1=RL_1 = \emptyset \in \text{R}:

אם L1L_1 לא ריקה אז קיימת מ"ט, MM, שעונה לתנאים הנ"ל. נראה שאפשר להכריע את HP על ידי MM:

בהינתן קלט (M,x)(\langle M' \rangle, x):

  • הרץ את MM על (M,x)(\langle M' \rangle, x) וקבל אמ"מ MM פלטה 1.

2. נראה ש-L2REL_2 \notin \text{RE} על ידי רדוקציה מ-HP\overline{\text{HP}}:

f(M,x)=(M1,Mx)f(\langle M \rangle, x) = (\langle M_1 \rangle, \langle M_x \rangle)

כאשר M1M_1 היא מ"ט שתמיד פולטת 1 ו-MxM_x על קלט ww:

  • מריצה את MM על xx במשך w|w| צעדים לכל היותר
  • אם MM עצרה פולטת 0 אחרת פולטת 1

נשים לב שאם MM עוצרת על xx אמ"מ קיים ww כך ש-fMx(w)=0f_{M_x}(w) = 0 ולכן (M,x)HP(M1,Mx)L2(\langle M \rangle, x) \in \overline{\text{HP}} \iff (\langle M_1 \rangle, \langle M_x \rangle) \in L_2

3. נראה ש-L3RERL_3 \in \text{RE} \setminus \text{R}:

שייכות ל-RE

מבצעים הרצה מבוקרת של M1M_1 ו-M2M_2 על כל המחרוזות (למשל לפי סדר לקסיקוגרפי) ומקבלים אמ"מ קיימת מחרוזת כך ששתי המכונות פלטו פלט זהה עליה.

נראה ש-L3RL_3 \notin \text{R} על ידי רדוקציה מ-HP:

f(M,x)=M1,Mxf(\langle M \rangle, x) = \langle M_1 \rangle, \langle M_x \rangle

כאשר M1M_1 מכונה שתמיד פולטת 1 ו-MxM_x על קלט ww:

  • מריצה את MM על xx
  • פולטת 1

נשים לב ש-

fMx(w)={1M halts on xundefinedotherwise f_{M_x}(w) = \begin{cases} 1 & M \text{ halts on } x \\ \text{undefined} & \text{otherwise} \end{cases}

ולכן (M,x)HP(M1,Mx)L3(\langle M \rangle, x) \in \text{HP} \iff (\langle M_1 \rangle, \langle M_x \rangle) \in L_3

1
Feedback