תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט רייס: קישורים פנימיים |
|||
שורה 41:
{{הוכחה|1=
נראה כי <math>L_S \notin R</math> על־ידי הרדוקציה <math>\text{HP} \le L_S</math>. כלומר, נניח על דרך השלילה <math>L_S \in R</math>, ונראה כי אפשר להכריע לכל מ"ט <math>M</math> וקלט <math>x</math>, האם <math>M</math> עוצרת על <math>x</math> (מה ש[[תורת_החישוביות/כריעות_שפות/
בלי הגבלת הכלליות, נניח כי ה[[תורת החישוביות/כריעות שפות|שפה הריקה]] אינה ב־<math>S</math> (כלומר
|