תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף

[[w:משפט רייס|משפט רייס]]
טוען שבהנתן קידוד של מ״ט <math>\langle M \rangle</math>, קשה לדעת מה השפה <math>L(M)</math> שהמכונה מכריעה.

למעשה, המשפט מגדיר משפחות של שפות <math>S</math> – כל שפה <math>L\in S</math> היא אוסף מכונות טיורינג שהשפה שהן מכריעות מקיימותמקיימת '''תכונה''' מסויימת, למשל, השפה שהן מכריעות היא ריקה, או השפה שהן מכריעות מכילה מספר זוגי של מילים, וכו'. המשפט מראה שאם התכונה הנ״ל אינה טריוויאלית, אז השפה <math>L</math> (שהיא, כאמור, אוסף קידודי מכונות הטיורינג ששפתן מקיימות את התכונה האמורה) אינה כריעה.

הגדרה: '''תכונה''' של שפות ב־REב־<math>RE</math> היא תת קבוצה <math>S\subseteq RE</math>.

בתור אוסף מ״ט שהשפה שלהן מקיימת את התכונה <math>S</math>.{{רווח קשיח|2}}}}

הערה: יש להבחין בין תכונה של שפות לבין תכונה של מכונות־טיורינג, כגון "למכונה יש מס' זוגי של מצבים". עבור <math>L</math> מסויימת תתכן <math>M_1</math> בעלת התכונה ו־<math>M_2</math> ללא התכונה כך שמתקיים <math>L=L(M_1)=L(M_2)</math>.

אם <math>S</math> טריוויאלית, אזי או שהיא אינה מכילה אף שפה, או שהיא מכילה את כל השפות ב־RE. עבור תכונה שכזו, השפה <math>L_S \in R</math>:

* אם <math>S=RE</math>, אזי כל שפה שמוכרעת ע״י מ"ט מקיימת את התכונה, ומשתמע שקידודי '''כל מ״ט''' יהיו ב־<math>L_S</math> , כלומר, <math>L_S=\Sigma^*</math> שגם היא שפה כריעה. (מקרה קצה: גם מחרוזות שאינן קידוד תקין של מ״ט מסמלות, לפי הגדרתנו, מ״ט שדוחה כל מילה בצעד הראשון. השפה של "מכונות" אלו היא <math>L(M)=\emptyset</math>, ושפה זו נמצאת ב־REב־<math>RE</math> ולכן גם ב־Sב־<math>S</math>. לכן, גם קידודי "מכונות" אלו שייכים ל־<math>L_S</math>.)

שאלה=וודא שהנך מבין מדוע אם <math>S</math> היא תכונה לא טריוויאלית, אז התכונה המשלימה לה, <math>\overline S</math>, גם היא לא טריוויאלית.

לכל תכונה לא טריוויאלית <math>S</math> של שפות ב־REב־<math>RE</math> מתקיים:{{רווח קשיח|10}} <math>L_S \notin R</math>{{רווח קשיח|10}}}}