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

\text{Palindromes} = \{ \langle M \rangle |\mid \text{any palindrome} \in L(M) \}.

S_P = \{ L |\mid L \in RE \bigwedge \text{any palindrome} \in L \}.

נגדיר את השפה <math>L_7 = \{ \langle M\rangle\mid |L(M)|=7\}</math>. {{ש}}
התכונה המתאימה היא <math>S=\{ L\in RE\mid |L|=7\}</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>.}}

להלן דוגמה לשימוש לאשגוי נכון.במשפט רייס:

החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט <math>M</math>. האם <math>M</math> תקבל כל קלט תוך מספר זוגי של צעדים?{{ש}}

כאן לא נוכל להמיר את הבעייההבעיה לפורמט מתאים לבעיית רייס, משום שמדובר בתכונה של מ"ט, לא תכונה של שפה. נקח מ"טמ״ט כלשהי, ונבנה מ"טמ״ט אחרת הנבדלת ממנה בכך שיש לה מצב התחלתי נוסף, ממנו עוברים למצב ההתחלתי המקורי. שתי המכונות מקבלות בדיוק אותה שפה, אך במספר שונה של צעדים.