ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Gran (שיחה | תרומות)
2,595 עריכות
Gran (שיחה | תרומות)
2,595 עריכות
שורה 123:
ללא תנאים נוספים, אם <math>S</math> תכונה לא טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>RE</math>. ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים#הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית|תרגיל: הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית]] תתבקש להוכיח את המשפט הבא:
{{משפט|
תוכן=באופן כללי, לתכונה לא-טריוויאלית <math>S</math> של שפות ב־RE, כך ש־<math>\emptyset\in S</math> מתקיים:{{רווח קשיח|10}} <math>L_S \notin RE</math> }}
 
(דהיינו, ישנה שפה <math>S</math> שעבורה ההחלטה איננה ב-<math>RE</math>). }}
 
עם זאת, ישנם תנאים נוספים ל-<math>S</math>, שקיומם מהווה תנאי מספיק והכרחי לכך ששאלת השייכות היא ב-<math>RE</math>.
{{משפט|תוכן=
בהנתן תכונה <math>S \subseteq RE</math>, אז <math>LSL_S \in RE</math> אמאם"ם מתקיימות כ"אכלל מהתכונותהתכונות הבאות:
# אםעבור שתי שפות <math>L, L' \in SRE</math>, וכןאם <math>L, L' \in RES</math>, וכןוגם <math>L' \subseteq L</math>, אז <math>L \in S</math>.
# אם <math>L \in S</math>, אז יש ל-ל־<math>L</math> תת-שפהתת־שפה סופית <math>L' \subseteq L</math> המקיימת <math>L' \in S</math>.
# שפתקיימת כל השפות הסופיות ב-<math>S</math> היא ב-<math>RE</math> (כלומר, יש מ"טמ״ט המונה כל שפה סופית ב-ב־<math>S</math>).
}}
 
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/כריעות_שפות/משפט_רייס"