Question

classification_r_re

עבור מ"ט דטרמיניסטית MM, נסמן ב M\overline{M} את המ"ט המתקבלת על ידי היפוך המצבים הסופים. כלומר המצב המקבל ב-MM הוא המצב הדוחה ב-M\overline{M} וההיפך.

עבור כל אחת מהשפות הבאות קבעו האם היא ב-RR, האם היא ב-RERE והאם היא ב-coREcoRE.

L1={M:w,wL(M)L(M)}L_1 = \{\langle M \rangle :\exists w,w \in L(M) \cap L(\overline{M})\}

L2={M:w,wL(M)L(M)}L_2 = \{\langle M \rangle :\exists w,w \in L(M) \cup L(\overline{M})\}

L3={M:w,wL(M)L(M)}L_3 = \{\langle M \rangle :\exists w,w \notin L(M) \cup L(\overline{M})\}

L4={M:w,wL(M)L(M)}L_4 = \{\langle M \rangle :\forall w,w \in L(M) \cup L(\overline{M})\}

1

Answers

1. מתקיים ש-L1=L_1 = \emptyset כיוון שאם MM מקבלת מילה מסוימת אז M\overline{M} בהכרח דוחה אותה, ולכן L1RL_1 \in \text{R}.

2. נשים לב שהתנאי שקול לכך שקיים קלט עבורו MM עוצרת, ולכן על ידי הרצה מבוקרת ניתן לקבל את L2L_2, כלומר L2REL_2 \in \text{RE}.

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

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

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

  • מריצה את MM על xx
  • מקבלת

נשים לב ש-

L(Mx)={ΣM halts on xotherwise L(M_x) = \begin{cases} \Sigma^* & M \text{ halts on } x \\ \emptyset & \text{otherwise} \end{cases}

ולכן

(M,x)HP    M halts on x    L(Mx)=Σ    w:wL(Mx)    MxL2(\langle M \rangle, x) \in \text{HP} \implies M \text{ halts on } x \implies L(M_x) = \Sigma^* \implies \exists w : w \in L(M_x) \implies M_x \in L_2

וגם

(M,x)/HP    M doesn’t halt on x    w  Mx does not halt on w    L(Mx)=L(Mx)=    Mx/L2(\langle M \rangle, x) \notin \text{HP} \implies M \text{ doesn't halt on } x \implies \forall w \; M_x \text{ does not halt on } w \implies L(M_x) = L(\overline{M_x}) = \emptyset \implies M_x \notin L_2

קל לראות שהרדוקציה ניתנת לחישוב.

3. נשים לב שהתנאי שקול לכך שקיים ww כך ש-MM לא עוצרת עליו. נראה ש-L3/REL_3 \notin \text{RE} על ידי רדוקציה מ-HP:

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

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

  • מריצה את MM על xx במשך w|w| צעדים ואם עצרה ממשיכה לרוץ, אחרת מקבלת.

נשים לב שאם MM לא עוצרת על xx אז L(Mx)=ΣL(M_x) = \Sigma^*

ואם MM עוצרת על xx אחרי kk צעדים אז על כל קלט באורך גדול או שווה ל-kk MxM_x לא עוצרת. לכן:

(M,x)HP    M halts on x    w:w/L(Mx)L(Mx)    MxL3(\langle M \rangle, x) \in \text{HP} \implies M \text{ halts on } x \implies \exists w: w \notin L(M_x) \cup L(\overline{M_x}) \implies M_x \in L_3

וגם

(M,x)/HP    M doesn’t halt on x    L(Mx)=Σ    Mx/L3(\langle M \rangle, x) \notin \text{HP} \implies M \text{ doesn't halt on } x \implies L(M_x) = \Sigma^* \implies M_x \notin L_3

קל לראות שהרדוקציה ניתנת לחישוב.

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

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

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

  • מריצה את MM על xx
  • מקבלת

נשים לב שאם MM לא עוצרת על xx אז MxM_x לא עוצרת על אף קלט ואם MM עוצרת על xx אז L(Mx)=ΣL(M_x) = \Sigma^*. לכן:

(M,x)HP    M doesn’t halt on x    Mx doesn’t halt     w:w/L(Mx)L(Mx)    MxL3(\langle M \rangle, x) \in \overline{\text{HP}} \implies M \text{ doesn't halt on } x \implies M_x \text{ doesn't halt } \implies \exists w: w \notin L(M_x) \cup L(\overline{M_x}) \implies M_x \in L_3

וגם

(M,x)/HP    M halts on x    L(Mx)=Σ    Mx/L3(\langle M \rangle, x) \notin \overline{\text{HP}} \implies M \text{ halts on } x \implies L(M_x) = \Sigma^* \implies M_x \notin L_3

קל לראות שהרדוקציה ניתנת לחישוב.

4. נשים לב ש-L4=L3L_4 = \overline{L_3} על כל המשתמע מכך.

1
Feedback