תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 130:
===שפה שאינה כריעה למחצה===
לסיום, נראה שימוש ברדוקציה כדי להראות שפה ספציפית שאינה ב־<math>RE\cup coRE</math>:
{{טענה|תוכן=נגדיר <math>L_{\Sigma^*} = \{ \langle M \rangle \mid L(M) = \Sigma^* \}</math>, אוסף כל המכונות שמקבלות כל מילה אפשרית ב־<math>\Sigma^*</math>. אזי מתקיים{{רווח קשיח|10}}
 
 
<center><math>L_{\Sigma^*} \notin RE \cup coRE</math></center>
 
}}
{{רווח קשיח|1}}}}
נוכיח טענה זו ע״י שימוש ברדוקציה ובמשפט הרדוקציה ההפכי. אם נוכל להראות רדוקציה אל <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>, כך שאם <math>M</math> עוצרת על 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 מבצעת כלהלן.: מריצה את <math>M</math> על x למשך <math>|w|</math> צעדים. אם <math>M</math> עצרה, <math>M_x</math> <u>דוחה</u>. קל לראות שאם M <u>לא עוצרת</u> על x, אז <math>M_x</math> מקבלת כל מילה ב־<math>\Sigma^*</math>.