תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ עריכה |
|||
שורה 63:
נשים לב שהרדוקציה אכן ברת חישוב - בהנתן <math>(\langle M \rangle, x)</math>, קל לבנות פונקציה המשרשרת את שתי המכונות ויוצרת את תיאור <math>M_x</math>. כמו כן, לפי הנחתנו בשלילה, הקריאה ל<math>Q</math> מסתיימת גם כן.
}}
==דוגמאות ליישומי משפט רייס==
# <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>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>.▼
==מניה רקורסיבית של שפות בעלות תכונה==
שורה 84 ⟵ 92:
ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים|תרגיל: הכרחיות תנאי 1 למניה רקורסיבית של שפות בעלות תכונה]], [[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים|תרגיל: הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונה]], ו[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים|תרגיל: הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונה]], תתבקש להראות שכ"א מתנאים אלה הכרחי להיות הבעיה ב-<math>RE</math>.
▲# <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>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>.
{{תורת החישוביות|מוגבל}}
| |||