תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
יצירת דף עם התוכן "{{תורת החישוביות}} ==מעבר על כל המצבים הנייטראליים במ"ט== נגדיר '''מצב נייטראלי''' של מ"ט כמצב..." |
←אופטימיזציית מ"ט: הרחבה |
||
שורה 8:
בהנתן בהנתן מ"ט <math>M</math> ומחרוזת <math>x</math>, ברצוננו לדעת האם אפשר לאפטם את <math>M</math> כך שזמן ריצתה יהיה פולינומי ב-<math>|x|</math>. האם זו בעיה כריעה?
==הגרסה השלילית של המשפט המורחב==
הוכח את המשפט הבא:
{{משפט|שם=משפט רייס המורחב|
תוכן=לכל תכונה לא טריוויאלית S של שפות ב־RE מתקיים:{{רווח קשיח|10}} <math>L_S \notin RE</math>}}
{{מוסתר|ta2 = right|הפתרון|2=
נובע מכייוון שראינו רדוקציה <math>\text{HP}\le L_S</math>, וכן ראינו <math>L_{\overline S} = \overline{L_S}</math>.{{ש}}
מאלה נובע בסופו של דבר ש־<math>\overline{\text{HP}}\le L_S</math> ומכאן ש־<math>L_S \notin RE</math> (משפט הרדוקציה ההפכי)
}}
| |||