תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט רייס: תקלדה |
|||
שורה 61:
# אם <math>M</math> עוצרת על x{{כ}}, אז <math>M_X</math> מתנהגת בדיוק כמו <math>M_0</math>{{כ}}. אם כך, <math>L(M_x)=L(M_0)\in S</math>, ו-<math>Q</math> תכריע ש-<math>M_x \in L_S</math>.
נשים לב שהרדוקציה אכן ברת חישוב - בהנתן <math>(\langle M \rangle, x)</math>, קל לבנות פונקציה
}}
| |||