ויקיספר

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

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