תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←שפה שאינה כריעה למחצה: הגהה, עיצוב |
|||
שורה 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 מבצעת כלהלן
|