Question

r_re
ld
hp

תזכורת: LD={MML(M)}\overline{L_D} = \{\langle M \rangle | \langle M \rangle \notin L(M)\}.

  1. הציגו הוכחה ישירה (מבלי להשתמש בשפות אחרות) ש-LDRE\overline{L_D} \notin RE.
  2. הוכיחו: HPLD\overline{HP} \leq \overline{L_D}.
1

Answers

1. נניח בשלילה ש-LDRE\overline{L_D} \in \text{RE}, כלומר קיימת מ"ט, MM, כך ש-L(M)=LDL(M) = \overline{L_D}. נשים לב ש:

MLD    M/L(M)\langle M \rangle \in \overline{L_D} \iff \langle M \rangle \notin L(M)

וזאת סתירה כי LD=L(M)\overline{L_D} = L(M).

2. נגדיר:

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

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

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

נשים לב ש-

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

ולכן:

(M,x)HP    M doesn’t halt on x    L(Mx)=    Mx/L(Mx)    MxLD(\langle M \rangle, x) \in \overline{HP} \implies M \text{ doesn't halt on } x \implies L(M_x) = \emptyset \implies \langle M_x \rangle \notin L(M_x) \implies \langle M_x \rangle \in \overline{L_D}

וגם

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

קל לראות ש-ff ניתנת לחישוב.

1
Feedback