תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דוגמאות ליישומי משפט רייס: הגהה |
מ ←דוגמאות ליישומי משפט רייס: עריכה |
||
שורה 95:
{{דוגמה|תוכן=
החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט <math>M</math>. האם אפשר לאפטם את <math>M</math> כך שזמן הריצה שלה בקבלת <math>x</math> יהיה
כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה
<center><math>
S_P = \{ L | L \in RE \bigwedge \exists_M \forall_x M \text{accepts } x \text{ in
</math></center>
כעת אפשר לראות שמדובר בתכונה של שפות, הגם שהן מוגדרות ע"י מכונות טיורינג. המשך דוגמה זו מופיע ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים#אופטימיזציית מ"ט|תרגיל: אופטימיזציית מ"ט]].
| |||