ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
שורה 68:
{{בעבודה}}
 
משפט רייס מאפשר בצורה קלה מאד להוכיח שבעיות רבות אינן כריעות. אם זאת, יש להשתמש בו בזהירות. כפי שצויין ב[[#תכונות של שפות|תכונות של שפות]], למרות שהחלטת התכונה פורמאלית מופעלת על ייצוג של מ"ט, התכונה היא למעשה של שפות, ובפרט שפות נתנות למניה רקורסיבית. כדי להשתמש במשפט רייס, יש לתרגם את השאלה כך שהיא פועלת על שפות נתנות למניה רקורסיבית. להלן מספר דוגמאות נכונות ושגויות לשימוש במשפט רייס.
# <math>L_\varepsilon = \{ \langle M \rangle \mid \varepsilon \in L(M)\}</math>
 
#:נגדיר את התכונה <math>S=\{ L\in RE \mid \varepsilon \in L\}</math>. S אינה טריוויאלית: <math>\Sigma^* \in S</math> ואילו <math>\emptyset \notin S</math> (וכאמור <math>\emptyset\in RE</math>). לפי משפט רייס <math>L_S \notin R</math>.
{{דוגמה|תוכן=
# <math>L_\emptyset = \{ \langle M\rangle\mid L(M)=\emptyset\}</math>
החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט <math>M</math>. האם <math>M</math> תקבל כל [[w:פלינדרום|פלינדרום]].
#:התכונה <math>S=\{\emptyset\}</math>, מכילה שפה אחת ולכן אינה טריוויאלית, ולפי המשפט <math>L_\emptyset \notin R</math>.
 
# <math>L_7 = \{ \langle M\rangle\mid |L(M)|=7\}</math>
הבעיה היא
#:נגדיר את התכונה <math>S=\{ L\in RE\mid |L|=7\}</math>. התכונה אינה טריוויאלית: <math>\Sigma^* \in RE, \Sigma^* \notin S</math>, וכן קיימת בה לפחות שפה אחת, למשל השפה <math>\{\varepsilon,0,1,00,11,000,111\} \in S</math>. ממשפט רייס נובע <math>L_7 \notin R</math>.▼
<center><math>
\text{Palindromes} = \{ \langle M \rangle | \text{any palindrome} \in L(M) \}.
</math></center>
כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה
 
<center><math>
S_P = \{ L | L \in RE \bigwedge \text{any palindrome} \in L \}.
</math></center>
כעת, בפורמט המתאים, נוכל לשים לב שמשפט רייס חל. התכונה איננה טריוויאלית: השפה (הנתנת למניה רקורסיבית)
<math>\Sigma^*</math>
בעלת התכונה, ואילו השפה הריקה איננה.}}
 
להלן עוד דוגמה לשימוש נכון.
{{דוגמה|תוכן=
▲#:נגדיר את התכונההשפה <math>SL_7 = \{ L\inlangle REM\rangle\mid |L(M)|=7\}</math>. התכונה אינה טריוויאלית:היא <math>S=\Sigma^*{ L\in RE, \Sigma^*mid |L|=7\notin S}</math>,. נשים לב וכןכי קיימת בה לפחות שפה אחת, למשל השפה <math>\{\varepsilon,0,1,00,11,000,111\} \in S</math>, אך <math>\Sigma^* \in RE, \Sigma^* \notin S</math>, ולכן התכונה איננה טריוויאלית. ממשפט רייס נובע <math>L_7 \notin R</math>.}}
 
להלן דוגמה לשימוש לא נכון.
 
 
{{בעבודה}}
 
==מניה רקורסיבית של שפות בעלות תכונה==
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/כריעות_שפות/משפט_רייס"