משפט רייס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הנדב הנכון (שיחה | תרומות) |
אין תקציר עריכה |
||
שורה 2:
באופן פורמלי, השפה <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>.
== הוכחת המשפט ==
| |||