תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←שימושים במשפט הרדוקציה: אי כריעות האלכסון |
←שימושים במשפט הרדוקציה: הארה על שתי שיטות ההוכחה |
||
שורה 126:
* <math>L_D, L_U, L_{HP}, \overline {L_D}, \overline{L_U}, \overline {L_\text{HP}}</math>
}}
{{הארה|השווה בין ההוכחה ש־<math>L_\text{HP} \notin R</math> כפי שהובאה בפרק [[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות|קיום שפות שאינן כריעות]] לבין ההוכחה לעיל של שפת האלכסון, בתוספת שרשרת הרדוקציות משפת האלכסון אל <math>L_\text{HP}</math>. ההוכחה ה"ישירה" למעשה מכילה את שרשרת הרדוקציות באופן אינהרנטי, ומבצעת את הליכסון המוביל לסתירה על המכונה שמוגדרת ע״י שרשרת הרדוקציות.}}
לסיום, נראה שפה ספציפית שאינה ב־<math>RE\cup coRE</math>:
| |||