תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפטים: עיצוב, הגהה, להשלים: הוכחת שפה האלכסון. |
←שימושים במשפט הרדוקציה: אי כריעות האלכסון |
||
שורה 107:
===שימושים במשפט הרדוקציה===
ראשית, נראה כי שפה מסויימת, שפת האלכסון, אינה כריעה. לאחר מכן, נראה שרשרת רדוקציות לשפות אחרות. ממשפט הרדוקציה (ההפכי) ינבע שכלל השפות אינן כריעות.
{{טענה|תוכן= {{רווח קשיח|5}}<math>\overline{L_D} \notin R</math>{{רווח קשיח|5}}}}
נראה, בשיטת הלכסון כי השפה <math>\overline{L_D} \notin R</math>. כזכור,
<center><math>\overline{L_D} = \{ \langle M \rangle \;\mid\; \langle M \rangle \notin L(M) \}</math></center>
נניח בשלילה ש־<math>\overline{L_D} \in R</math> ולכן קיימת מ״ט <math>M_D</math> שמכריעה את <math>\overline{L_D}</math>.
נביט על המחרוזת <math>\langle M_D \rangle</math>. נניח כי <math>\langle M_D \rangle \in \overline{L_D}</math> אזי מהגדרת השפה נובע כי <math>\langle M_D \rangle \notin L(M_D)</math>. במילים אחרות, אם מריצים את <math>M_D</math> על המחרוזת <math>\langle M_D \rangle</math>, המכונה לא תקבל את הקלט, ובפרט היא '''תדחה אותו''' (כי היא מכונה מכריעה). אבל, זו סתירה, כי הנחנו ש־<math>\langle M_D \rangle \in \overline{L_D}</math>, כלומר, הקלט בשפה ו־<math>M_D</math> צריכה לקבל אותו מכיוון שהיא מכריעה את השפה.
נחזור על הטיעון עבור המקרה השני. אם מניחים כי המחרוזת אינה בשפה, <math>\langle M_D \rangle \notin \overline{L_D}</math>, אזי המכונה <math>M_D</math> צריכה '''לדחות''' את הקלט <math>\langle M_D \rangle</math>. מכאן ש־<math>M_D</math> אינה מקבלת את המחרוזת של עצמה, ולכן היא שייכת ל־<math>\overline{L_D}</math>, או באופן יותר מדוייק, הקידוד שלה נמצא בשפה זו, <math>\langle M_D \rangle \in \overline{L_D}</math> וזו סתירה להנחה.
נשים לב ש־<math>R</math> סגורה למשלים. לפיכך, מכיוון ש־<math>\overline{L_D} \notin R</math>, כך גם השפה המשלימה <math>L_D \notin R</math>.
| |||