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

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