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

* אם <math>S=\emptyset</math>, אזי אף שפה לא מקיימת את התכונה, לכן <math>L_S=\emptyset</math>, וזו שפה כריעה.

* אם <math>S=RE</math>, אזי כל שפה שמוכרעת ע״י מ"ט מקיימת את התכונה, ומשתמע שקידודי '''כל מ״ט''' יהיו ב־<math>L_S</math> , כלומר, <math>L_S=\Sigma^*</math> שגם היא שפה כריעה. (מקרה קצה: גם מחרוזות שאינן קידוד תקין של מ״ט מסמלות, לפי הגדרתנו, מ״ט שדוחה כל מילה בצעד הראשון. השפה של "מכונות" אלו היא <math>L(M)=\emptyset</math>, ושפה זו נמצאת ב־RE ולכן גם ב־S. לכן, גם קידודי "מכונות" אלו שייכים ל־<math>L_S</math>.)

 

==משפט רייס==