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

 

==דוגמאות ליישומי משפט רייס==

# <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>.