תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←משפט רייס: יש כאן ניואנס, שהמשלים של השפה של S זהה לשפה של המשלים של S |
|||
שורה 40:
נראה כי <math>L_S \notin R</math> על־ידי הרדוקציה <math>\text{HP} \le L_S</math>. מכיוון שראינו ש־<math>\text{HP}\notin R</math> נובע המשפט.
<math>\emptyset \notin S</math>).
אחרת, פשוט נוכיח את המשפט לגבי התכונה המשלימה <math>\overline S</math> - ▼
כפי שראינו לעיל, גם המשלים של תכונה לא-טריוויאלית הוא תכונה לא טריוויאלית, והכרעה רקורסיבית לגבי <math>S</math> שקולה להכרעה רקורסיבית לגבי <math>\overline S</math>.▼
היות ש־<math>S</math> אינה טריוויאלית, בהכרח קיימת שפה <math>L_0</math> כך ש־<math>L_0 \in S</math>. מכיוון ש־<math>S</math> היא קבוצה של שפות ב־<math>RE</math>, גם <math>L_0 \in RE</math>, ונניח כי <math>M_0</math> היא מ״ט המקבלת אותה.
שורה 63 ⟵ 59:
#:: אם <math>(\langle M \rangle, x)\in\text{HP}</math> אז M עוצרת על x, ומתקיים <math>L(M_x)=L_0\in S</math>, ולכן <math>\langle M_x\rangle \in L_S</math>
#:: אם <math>(\langle M \rangle, x)\notin\text{HP}</math> אז M לא עוצרת על x, ומתקיים <math>L(M_x)=\emptyset\notin S</math>, ולכן <math>\langle M_x\rangle \notin L_S</math>
לסיום, הנחנו לעיל ש־<math>\emptyset \notin S</math>, אך מה קורה אם הנחה זו אינה נכונה?
▲כפי שראינו לעיל, גם המשלים של תכונה לא-טריוויאלית הוא תכונה לא טריוויאלית, והכרעה רקורסיבית לגבי <math>S</math> שקולה להכרעה רקורסיבית לגבי <math>\overline S</math>. באופן פורמלי,
נביט בתכונה המשלימה <math>\overline S = RE \smallsetminus S</math>. מתקיים <math>\emptyset \notin \overline{S}</math> ולכן, כפי שהוכחנו <math>L_{\overline{S}}\notin R</math>. נשים לב ש
<center><math>L_{\overline{S}}=\{\langle M\rangle \mid L(M) \in \overline S\} = \{\langle M\rangle \mid L(M) \notin S\} = \overline{L_S}</math></center>
כלומר <math>\overline {L_S} \notin R</math>, ומכיוון ש־R סגורה למשלים, זו הוכחה ש־<math>L_S \notin R</math> כנדרש.
}}
| |||