תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ הגהה |
|||
שורה 2:
[[w:משפט רייס|משפט רייס]]
טוען שבהנתן קידוד של מ״ט <math>\langle M \rangle</math>, קשה לדעת מה השפה <math>L(M)</math> שהמכונה מכריעה. ==תכונות של שפות==
הגדרה: '''תכונה''' של שפות
דוגמאות:
שורה 18 ⟵ 19:
בהנתן תכונה <math>S\subseteq RE</math> נגדיר את השפה <math>L_S \ </math>
<center><math>L_S = \{ \langle M \rangle \mid L(M)\in S\}</math></center>
בתור אוסף מ״ט שהשפה שלהן מקיימת את התכונה <math>S</math>.{{רווח קשיח|2}}}}
הערה: יש להבחין בין תכונה של שפות לבין תכונה של מכונות־טיורינג, כגון "למכונה יש מס' זוגי של מצבים". עבור <math>L</math> מסויימת תתכן <math>M_1</math> בעלת התכונה ו־<math>M_2</math> ללא התכונה כך שמתקיים <math>L=L(M_1)=L(M_2)</math>.
{{הגדרה|תוכן=
S תיקרא '''טריוויאלית''' אם <math>S=\emptyset</math> או <math>S=RE</math>{{רווח קשיח|2}}}}
אם <math>S</math> טריוויאלית, אזי או שהיא אינה מכילה אף שפה, או שהיא מכילה את כל השפות ב־RE. עבור תכונה שכזו, השפה <math>L_S \in R</math>:
* אם <math>S=\emptyset</math>, אזי אף שפה לא מקיימת את התכונה, לכן <math>L_S=\emptyset</math>, וזו שפה כריעה.
* אם <math>S=RE</math>, אזי כל שפה שמוכרעת ע״י מ"ט מקיימת את התכונה, ומשתמע שקידודי '''כל מ״ט''' יהיו ב־<math>L_S</math> , כלומר, <math>L_S=\Sigma^*</math> שגם היא שפה כריעה. (מקרה קצה: גם מחרוזות שאינן קידוד תקין של מ״ט מסמלות, לפי הגדרתנו, מ״ט שדוחה כל מילה בצעד הראשון. השפה של "מכונות" אלו היא <math>L(M)=\emptyset</math>, ושפה זו נמצאת
{{תרגיל|יישור=ימין|
שאלה=וודא שהנך מבין מדוע אם <math>S</math> היא תכונה לא טריוויאלית, אז התכונה המשלימה לה, <math>\overline S</math>, גם היא לא טריוויאלית.
}}
שורה 37 ⟵ 38:
{{משפט|תוכן=
לכל תכונה לא טריוויאלית <math>S</math> של שפות
{{הוכחה|1=
|