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