תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←משפט רייס: יש כאן ניואנס, שהמשלים של השפה של S זהה לשפה של המשלים של S |
מ ←דוגמאות ליישומי משפט רייס: עיצוב |
||
שורה 77:
הבעיה היא
<center><math>
\text{Palindromes} = \{ \langle M \rangle
</math></center>
כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה
<center><math>
S_P = \{ L
</math></center>
כעת, בפורמט המתאים, נוכל לשים לב שמשפט רייס חל. התכונה איננה טריוויאלית: השפה (הנתנת למניה רקורסיבית)
שורה 102:
{{דוגמה|תוכן=
החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט <math>M</math>. האם אפשר לאפטם את <math>M</math> כך שזמן הריצה שלה בקבלת <math>x</math> יהיה
כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה
<center><math>
S_P = \{ L
</math></center>
כעת אפשר לראות שמדובר בתכונה של שפות, הגם שהן מוגדרות ע"י מכונות טיורינג. המשך דוגמה זו מופיע ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים#אופטימיזציית מ"ט|תרגיל: אופטימיזציית מ"ט]].
| |||