Question

r_re

עבור שפות L1,L2L_1, L_2 נגדיר את ההפרש הסימטרי שלהן L1L2L_1 \triangle L_2 כאוסף המילים xx כך ש-xL1L2x \in L_1 \setminus L_2 או xL2L1x \in L_2 \setminus L_1 (כלומר אוסף המילים השייכות בדיוק לאחת מבין שתי השפות L1,L2L_1, L_2).

עבור אוסף מכונות C={M1,M2,}C = \{\langle M_1 \rangle, \langle M_2 \rangle, \dots\} המכיל לפחות שני קידודים של מכונות, נאמר ש-DD מבחין של CC אם DD מ"ט המקבלת כקלט זוג קידודי מכונות (M1,M2)(\langle M_1 \rangle, \langle M_2 \rangle), ואם M1,M2CM_1, M_2 \in C אז DD פולטת xL(M1)L(M2)x \in L(M_1) \triangle L(M_2) אם קיים כזה, ואחרת DD לא עוצרת.

אם (M1,M2)(\langle M_1 \rangle, \langle M_2 \rangle) לא שתיהן ב-CC, המבחין DD יכול להתנהג איך שהוא רוצה.

הערה: שימו לב ש-DD לא יכול לקבוע איזה מכונות נמצאות באוסף ואיזה לא, אבל זה לא משנה מכיוון שאם אחת מהן לא ב-CC, כל התנהגות של DD מתקבלת.

בכל אחד מהסעיפים הבאים קבעו האם קיים מבחין DD לכל אוסף מכונות CC המקיים את התנאים בסעיף:

1. CC אוסף קידודי מכונות כלשהו.

2. CC אוסף קידודי מכונות כך שלכל MC\langle M \rangle \in C מתקיים L(M)RL(M) \in \text{R}.

3. CC המקיים שלכל MC\langle M \rangle \in C, MM מכריעה את השפה L(M)L(M).

1

Answers

1. נראה שאם היה קיים כזה אז היינו יכולים לקבל את HP\overline{\text{HP}}. עבור קלט (M,x)(\langle M \rangle, x) נגדיר שתי מ"ט, MΣ,MxM_{\Sigma^*}, M_x כאשר MΣM_{\Sigma^*} מ"ט שמקבלת הכל ו-MxM_x על קלט yy:

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

נשים לב ש-MΣMx̸=M_{\Sigma^*} \triangle M_x \neq \emptyset אמ"מ MM לא עוצרת על xx.

2. ראו סעיף 1.

3. נתאר מפריד מתאים, DD על קלט M1,M2\langle M_1 \rangle, \langle M_2 \rangle עובר על כל ה-xx בסדר לקסיקוגרפי ומקבל אמ"מ אחת המכונות מקבלת את xx והשניה דוחה. נשים לב שאם אכן שתי המכונות באוסף אז הן עוצרות לכל xx.

1
Feedback