תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←שימושים במשפט הרדוקציה: הארה על שתי שיטות ההוכחה |
←שימושים במשפט הרדוקציה: הרחבה: דוגמא לשפה מחוץ למחלקות החצ-כריעות |
||
שורה 128:
{{הארה|השווה בין ההוכחה ש־<math>L_\text{HP} \notin R</math> כפי שהובאה בפרק [[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות|קיום שפות שאינן כריעות]] לבין ההוכחה לעיל של שפת האלכסון, בתוספת שרשרת הרדוקציות משפת האלכסון אל <math>L_\text{HP}</math>. ההוכחה ה"ישירה" למעשה מכילה את שרשרת הרדוקציות באופן אינהרנטי, ומבצעת את הליכסון המוביל לסתירה על המכונה שמוגדרת ע״י שרשרת הרדוקציות.}}
===שפה שאינה כריעה למחצה===
לסיום, נראה שימוש ברדוקציה כדי להראות שפה ספציפית שאינה ב־<math>RE\cup coRE</math>:
{{טענה|תוכן=נגדיר <math>L_{\Sigma^*} = \{ \langle M \rangle \mid L(M) = \Sigma^* \}</math>, אזי מתקיים{{רווח קשיח|10}}
<center><math>L_{\Sigma^*} \notin RE \cup coRE</math></center>
}}
נוכיח טענה זו ע״י שימוש ברדוקציה ובמשפט הרדוקציה ההפכי. אם נוכל להראות רדוקציה אל <math>L_{\Sigma^*}</math>
משפה שאינה ב־RE, וגם משפה (אחרת) שאינה ב־coRE, אז ישתמע ש<math>L_{\Sigma^*}</math> אינה ב־RE וגם אינה ב־coRE, כנדרש. להלן עיקרי הרדוקציה. הפרטים המלאים נשארים כתרגיל לקורא.
* <math>HP \le L_{\Sigma^*}</math>: בעזרת הקלט <math>(\langle M \rangle, x)</math> נבנה מכונה חדשה <math>M_x</math> שאם M עוצרת על x אז <math>M_x</math> מקבלת כל קלט שלה, ואחרת, <math>M_x</math> אינה עוצרת.
* <math>\overline{HP} \le L_{\Sigma^*}</math>: בעזרת הקלט <math>(\langle M \rangle, x)</math> נבנה מכונה <math>M_x</math> שעל הקלט w מבצעת כלהלן. מריצה את M על x למשך <math>|w|</math> צעדים. אם M עצרה, <math>M_x</math> <u>דוחה</u>. קל לראות שאם M <u>לא עוצרת</u> על x, אז <math>M_x</math> מקבלת כל מילה ב־<math>\Sigma^*</math>.
{{תורת החישוביות|מוגבל}}
| |||