ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Gran (שיחה | תרומות)
2,595 עריכות
שורה 36:
הוכח את המשפט הבא:
{{משפט|
תוכן=באופן כללי, לתכונה לא-טריוויאלית <math>S</math> של שפות ב־RE עבורה <math>\emptyset\in S</math> מתקיים:{{רווח קשיח|10}} <math>L_S \notin RE</math> .}}
 
(דהיינו, ישנה שפה <math>S</math> שעבורה ההחלטה איננה ב-<math>RE</math>). }}
 
{{מוסתר|ta2 = right|הפתרון|2=
נובעבהוכחת מכייווןמשפט שראינורייס ראינו רדוקציה <math>\text{HP}\le L_S</math>,. וכןקל לראות שעבור התכונה המשלימה מתקיים ראינו <math>L_{\overline S} = \overline{L_S}</math>.{{ש}}
מאלה נובע בסופו של דבר ש־<math>\overline{\text{HP}}\le L_S</math> ומכאן ש־<math>L_S \notin RE</math> (משפט הרדוקציה ההפכי)
}}
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/כריעות_שפות/משפט_רייס/תרגילים"