משפט רייס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ קישור |
אין תקציר עריכה |
||
שורה 3:
באופן פורמלי, השפה
<div style="text-align: center;"><math>L= \{ \langle M\rangle \mid L(M) \in S\}</math></div>
הינה שפה '''[[כריעות|בלתי כריעה]]''', אם <math>\ S</math> הינה קבוצה '''לא-טריוויאלית''' של שפות.
הקבוצה <math>\ S</math> תחשב טריוויאלית אם היא הקבוצה הריקה (אינה מכילה אף שפה), או קבוצת כלל השפות. הסימון <math>\langle M\rangle</math> מציין מחרוזת בינארית המהווה קידוד של [[מכונת טיורינג]] <math>\ M</math>.
== הוכחת המשפט ==
| |||