תורת החישוביות/כריעות שפות/משפט רייס

משפט רייס טוען שבהנתן קידוד של מ״ט $⟨M⟩$, קשה לדעת האם השפה $L(M)$ מקיימת תכונה לא-טריוויאלית כלשהי (מושג שנגדירו במדוייק בהמשך). זהו כלי עזר חזק בהוכחה שבעיות אינן כריעות או אפילו נתנות למניה רקורסיבית.

בתכונות של שפות נגדיר במדוייק מהן תכונות של שפות, ובפרט מהן תכונות לא-טריוויאליות שלהן. במשפט רייס נוכיח שההחלטה האם לשפת המ"ט ישנה תכונה כזו - איננה כריעה. בדוגמאות ליישומי משפט רייס נראה דוגמאות לשימוש נכון ושגוי במשפט. במניה רקורסיבית של שפות בעלות תכונה נוכיח שההחלטה האם לשפת המ"ט יש תכונה לא טריוויאלית - בעקרון איננה אפילו נתנת למניה רקורסיבית (ונדון במקרים מיוחדים בהם היא כן).

תכונות של שפות

הגדרה: תכונה של שפות ב־$RE$ היא תת קבוצה $S\subseteq RE$.

דוגמאות:

1. התכונה "(כל השפות כך ש...) $\epsilon$ שייך לשפה" היא תת הקבוצה $S=\{L\mid L\in RE,\epsilon \in L\}$
2. התכונה "(כל השפות כך ש...) השפה היא סופית" היא תת הקבוצה $L\}$ היא סופית $S=\{L\mid$
3. התכונה "השפה היא ${\mathrm{\Sigma }}^{*}$" היא תת הקבוצה $S=\{L\mid L={\mathrm{\Sigma }}^{*}\}$

בתכונה האחרונה קיימת רק שפה אחת, אבל נשים לב שקיימות אינסוף מ״ט שמקבלות את השפה הנ״ל.

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

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

• אם $S=\mathrm{\varnothing }$, אזי אף שפה לא מקיימת את התכונה, לכן $L_S=\mathrm{\varnothing }$, וזו שפה כריעה.
• אם $S=RE$, אזי כל שפה שמתקבלת ע״י מ"ט מקיימת את התכונה, ומשתמע שקידודי כל מ״ט יהיו ב־$L_S$ , כלומר, $L_S={\mathrm{\Sigma }}^{*}$ שגם היא שפה כריעה. (מקרה קצה: גם מחרוזות שאינן קידוד תקין של מ״ט מסמלות, לפי הגדרתנו, מ״ט שדוחה כל מילה בצעד הראשון. השפה של "מכונות" אלו היא $L(M)=\mathrm{\varnothing }$, ושפה זו נמצאת ב־$RE$ ולכן גם ב־$S$. לכן, גם קידודי "מכונות" אלו שייכים ל־$L_S$.)

משפט רייס

המשפט הבא מראה כי לא ניתן להכריע בעזרת מ״ט האם השפה של מכונה מסויימת מקיימת או לא תכונה לא טריוויאלית S. תבנית:משפט תבנית:הוכחה

דוגמאות ליישומי משפט רייס

משפט רייס מאפשר בצורה קלה מאד להוכיח שבעיות רבות אינן כריעות. עם זאת, יש להשתמש בו בזהירות. כפי שצויין בתכונות של שפות, למרות שהחלטת התכונה פורמאלית מופעלת על ייצוג של מ"ט, התכונה היא למעשה של שפות, ובפרט שפות ניתנות למניה רקורסיבית. כדי להשתמש במשפט רייס, יש לתרגם את השאלה כך שהיא פועלת על שפות נתנות למניה רקורסיבית. להלן מספר דוגמאות נכונות ושגויות לשימוש במשפט רייס (בדף התרגילים אפשר למצוא דוגמאות נוספות).

תבנית:מבנה תבנית

להלן עוד דוגמה לשימוש נכון.

להלן דוגמה לשימוש שגוי במשפט רייס:

מאידך, נשים לב שלמרות שמשפט רייס מדבר על שפות, עצם העובדה שמ"ט מופיעות בהגדרת שפה, איננה פוסלת את השימוש במשפט באופן אוטומטי. פשוט צריך לשים לב האם אכן מדובר בתכונה של שפה. להלן דוגמה לשימוש נכון.

תבנית:מבנה תבנית

מניה רקורסיבית של שפות בעלות תכונה

בחלק קודם ראינו שאם התכונה $S$ איננה טריוויאלית, אז שאלת השייכות ל-$L_S$ איננה ב-$R$. בחלק זה נעסוק בשאלה מהם התנאים ל-$S$ כך ששאלת השייכות ל-$L_S$ תהיה ב-$RE$.

ללא תנאים נוספים, אם $S$ תכונה לא טריוויאלית, אז שאלת השייכות ל-$L_S$ איננה ב-$RE$. בתרגיל: הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית תתבקש להוכיח את המשפט הבא: תבנית:משפט

עם זאת, ישנם תנאים נוספים ל-$S$, שקיומם מהווה תנאי מספיק והכרחי לכך ששאלת השייכות היא ב-$RE$. תבנית:משפט

בתרגיל: הכרחיות תנאי 1 למניה רקורסיבית של שפות בעלות תכונה, תרגיל: הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונה, ותרגיל: הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונה, תתבקש להראות שכ"א מתנאים אלה הכרחי להיות הבעיה ב-$RE$.

כעת נראה שתנאים אלה מספיקים לכך שההחלטה ב-$RE$. תבנית:הוכחה

קישורים חיצוניים

• על הבעיה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית
• משפט רייס הגרסה המלאה

תבנית:תורת החישוביות