Question

r_re

תזכורת: Lk={M:L(M)k}L_{\geq k} = \{\langle M \rangle : |L(M)| \geq k\}

הוכיחו או הפריכו את הטענות הבאות:

  1. קיימת מ"ט MM כך ש-L(M)=1020|L(M)| = 10^{20}.
  2. קיימת מ"ט MM כך ש-L4L(M)L3L_{\geq 4} \subset L(M) \subset L_{\geq 3}.
  3. קיימת מ"ט MM כך ש-L3L(M)L4L_{\leq 3} \subset L(M) \subset L_{\leq 4}.
1

Answers

1. נכון, בפרט, לכל שפה סופית קיימת מ"ט שמכריעה אותה.

2. נכון, נראה מ"ט כזאת, MM.

תהי M3M_3 מ"ט כלשהי אבל קבועה כך ש-L(M3)=3|L(M_3)| = 3, המ"ט MM על קלט M\langle M' \rangle

  • אם M=M3\langle M' \rangle = \langle M_3 \rangle דוחה.
  • מבצעת הרצה מבוקרת של MM' על כל הקלטים ואם MM' קיבלה 3 קלטים מקבלת.

נשים לב ש-L4L(M)=L3{M3}L3L_{\geq 4} \subset L(M) = L_{\geq 3} \setminus \{\langle M_3 \rangle \} \subset L_{\geq 3}.

3. נניח בשלילה שקיימת MM כזאת ונראה רדוקציה HPL(M)\overline{HP} \leq L(M):

f(M,x)=<MM>f(\langle M' \rangle, x) = <M_{M'}>

כאשר MMM_{M'} על קלט ww:

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

נשים לב ש-

L(MM)={ΣMhalts on xotherwise L(M_{M'}) = \begin{cases} \Sigma^* & M'\; \text{halts on } x \\ \emptyset & \text{otherwise} \end{cases}

ולכן MML(M,x)M_{M'} \in L \iff (M', x).

1
Feedback