Question

spring_18_a
r_re

עבור מכונת טיורינג, MM, נסמן ב-R(M)R(M) את קובצת המילים אותן MM דוחה, כלומר }\}MM דוחה את xx R(M)={xΣ:R(M) = \{x \in \Sigma^* :

1. תארו בקצרה זוג מכונות M,MM, M' כך ש-R(M)̸=R(M)R(M) \neq R(M') אבל L(M)=L(M)L(M) = L(M').

לכל אחת מהשפות הבאות קבעו אם היא ב-R\text{R} והאם היא ב-RE\text{RE}:

2. }\}קיימת M̸=MM' \neq M כך ש-R(M)=R(M)R(M) = R(M') L1={M:L_1 = \{\langle M \rangle :

3. L2={M:R(M)2}L_2 = \{\langle M \rangle : |R(M)| \geq 2\}

4. }\}קיימת M̸=MM' \neq M כך ש-R(M)=R(M)R(M) = R(M') ובנוסף L3={M:L(M)̸=L(M)L_3 = \{ \langle M \rangle : L(M) \neq L(M')

1

Answers

1. המכונה שדוחה הכל והמכונה שלא עוצרת.

2. נשים לב שלכל מכונה קיימת מכונה עם קידוד שונה שמבצעת בדיוק אותו דבר ולכן L1=ΣRL_1 = \Sigma^* \in \text{R}.

3. השפה שייכת ל-RE\text{RE} כיוון שניתן לבצע הרצה מבוקרת על כל המחרוזות בסדר לקסיקוגרפי ולקבל את MM אחרי שהיא דחתה 2 קלטים.

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

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

כאשר MxM_x על קלט yy:

  • מריצה את MM על xx
  • דוחה את yy

קל לראות ש-(M,x)HP    MxL2(\langle M \rangle, x) \in \text{HP} \iff \langle M_x \rangle \in L_2.

נראה ש-L3/REL_3 \notin \text{RE} על ידי רדוקציה מ-HP\overline{\text{HP}}:

כאשר MxM_x על קלט yy:

  • מריצה את MM על xx
  • דוחה את yy

נשים לב שמכונה שדוחה את כל המילים תמיד השפה שלה ריקה ולכן היא לא שייכת ל-L3L_3, לעומת זאת מכונה שלא דוחה אף מילה והשפה שלה ריקה שייכת ל-L3L_3 (בגלל מכונה שמקבלת הכל למשל), ולכן (M,x)HP    MxL2(\langle M \rangle, x) \in \overline{\text{HP}} \iff \langle M_x \rangle \in L_2.

1
Feedback