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

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

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

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

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

דוגמאות:

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

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

הגדרה: בהנתן תכונה $S\subseteq RE$ נגדיר את השפה $L_{S}\$ $L_{S}=\{\langle M\rangle \mid L(M)\in S\}$ בתור אוסף מ״ט שהשפה שלהן מקיימת את התכונה $S$.

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

הגדרה: S תיקרא טריוויאלית אם $S=\emptyset$ או $S=RE$

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

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

תרגיל : וודא שהנך מבין מדוע אם $S$ היא תכונה לא טריוויאלית, אז התכונה המשלימה לה, ${\overline {S}}$, גם היא לא טריוויאלית.

משפט רייס

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

משפט: לכל תכונה לא טריוויאלית S של שפות ב־RE מתקיים:           $L_{S}\notin R$

הוכחה: נראה כי $L_{S}\notin R$ על־ידי הרדוקציה ${\text{HP}}\leq L_{S}$. כלומר, נניח על דרך השלילה $L_{S}\in R$, ונראה כי אפשר להכריע לכל מ"ט $M$ וקלט $x$, האם $M$ עוצרת על $x$ (מה שידוע שאינו נכון).

בלי הגבלת הכלליות, נניח כי השפה הריקה אינה ב־$S$ (כלומר $\emptyset \notin S$). אחרת, פשוט נוכיח את המשפט לגבי התכונה המשלימה ${\overline {S}}$. כפי שראינו לעיל, גם המשלים של תכונה לא-טריוויאלית הוא תכונה לא טריוויאלית, והכרעה רקורסיבית לגבי $S$ שקולה להכרעה רקורסיבית לגבי ${\overline {S}}$.

היות ש־$S$ אינה טריוויאלית, בהכרח קיימת שפה $L_{0}$ כך ש־$L_{0}\in S$. מכיוון ש־$S$ היא קבוצה של שפות ב־$RE$, גם $L_{0}\in RE$, ונניח כי $M_{0}$ היא מ"ט המקבלת אותה.

נגדיר מ״ט $M_{x}$ הפועלת כך: בהנתן קלט $w$, המ״ט $M_{x}$,

1. מריצה את $M$ על $x$ (ומתעלמת מהתוצאה), ואז
2. מריצה את $M_{0}$ על $w$, ומקבלת/דוחה כמותה

מהנחתנו בשלילה ש־$L_{S}\in R$, נובע שקיימת מ"ט רקורסיבית $Q$ המכריעה את $L_{S}$. כדי להכריע האם $M$ עוצרת על $x$, נשאל את $Q$ האם $M_{x}\in L_{S}$:

1. אם $M$ איננה עוצרת על $x$, אז גם $M_{x}$ איננה עוצרת על אף $w$. אם כך, $L(M_{x})=\emptyset \notin S$, ו־$Q$ תכריע ש־$M_{x}\notin L_{S}$.
2. אם $M$ עוצרת על x‏, אז $M_{X}$ מתנהגת בדיוק כמו $M_{0}$‏. אם כך, $L(M_{x})=L(M_{0})\in S$, ו־$Q$ תכריע ש־$M_{x}\in L_{S}$.

נשים לב שאכן ניתן לבנות את $M_{x}$: בהנתן $(\langle M\rangle ,x)$, קל לבנות מ״ט המשרשרת את שתי המכונות ויוצרת את תיאור $M_{x}$. כמו כן, לפי הנחת השלילה, הקריאה ל־$Q$ עוצרת על כל קלט.

כדאי לדעת: באופן פורמלי, ההוכחה לעיל שקולה להגדרת פונקציית הרדוקציה $f(\langle M\rangle ,x)=\langle M_{x}\rangle$, ושימוש במשפט הרדוקציה ההפכי. קל לראות שפונקציית הרדוקציה בת־חישוב ומלאה (מקרה הקצה בו $\langle M\rangle$ אינו קידוד תקין, יוגדר כפלט $\langle M_{0}\rangle$). תקפות הרדוקציה נובעת מ: אם $(\langle M\rangle ,x)\in {\text{HP}}$ אז M עוצרת על x, ומתקיים $L(M_{x})=L_{0}\in S$, ולכן $\langle M_{x}\rangle \in L_{S}$ אם $(\langle M\rangle ,x)\notin {\text{HP}}$ אז M לא עוצרת על x, ומתקיים $L(M_{x})=\emptyset \notin S$, ולכן $\langle M_{x}\rangle \notin L_{S}$

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

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

דוגמה: החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט $M$. האם $M$ תקבל כל פלינדרום. הבעיה היא ${\text{Palindromes}}=\{\langle M\rangle \mid {\text{any palindrome}}\in L(M)\}.$ כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה $S_{P}=\{L\mid L\in RE\bigwedge {\text{any palindrome}}\in L\}.$ כעת, בפורמט המתאים, נוכל לשים לב שמשפט רייס חל. התכונה איננה טריוויאלית: השפה (הנתנת למניה רקורסיבית) $\Sigma ^{*}$ בעלת התכונה, ואילו השפה הריקה איננה.

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

דוגמה: נגדיר את השפה $L_{7}=\{\langle M\rangle \mid |L(M)|=7\}$. התכונה המתאימה היא $S=\{L\in RE\mid |L|=7\}$. נשים לב כי קיימת בה לפחות שפה אחת, למשל השפה $\{\varepsilon ,0,1,00,11,000,111\}\in S$, אך $\Sigma ^{*}\in RE,\Sigma ^{*}\notin S$, ולכן התכונה איננה טריוויאלית. ממשפט רייס נובע $L_{7}\notin R$.

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

דוגמה: החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט $M$. האם $M$ תקבל כל קלט תוך מספר זוגי של צעדים? (כלומר: $L=\{\langle M\rangle \mid M{\text{ accepts all }}x\in \Sigma ^{*}{\text{ in even number of steps }}\}$) כאן לא נוכל להמיר את הבעיה לפורמט מתאים לבעיית רייס, משום שמדובר בתכונה של מ"ט, לא תכונה של שפה. נקח מ״ט כלשהי, ונבנה מ״ט אחרת הנבדלת ממנה בכך שיש לה מצב התחלתי נוסף, ממנו עוברים למצב ההתחלתי המקורי. שתי המכונות מקבלות בדיוק אותה שפה, אך במספר שונה של צעדים.

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

דוגמה: החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ״ט $M$. האם אפשר לבצע אופטימיזציה למכונה, כך לאחר האופטימיזציה, זמן הריצה שידרש לקבלת קלט $x$ כלשהו יהיה קצר מאורך הקלט $|x|$? לכאורה הבעיה עוסקת במכונה עצמה, אבל למעשה היא עוסקת בתכונה של השפה המתקבלת. כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה באופן הבא $S_{P}=\{L\mid L\in RE\bigwedge \exists _{M}\forall _{x}M{\text{ accepts }}x{\text{ in less than }}|x|{\text{ steps}}\}.$ כעת אפשר לראות שמדובר בתכונה של שפות, הגם שהן מוגדרות ע״י מכונות טיורינג. המשך דוגמה זו מופיע בתרגיל: אופטימיזציית מ"ט.

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

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

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

משפט: עבור כל תכונה לא-טריוויאלית $S$ של שפות ב־$RE$, כך ש־$\emptyset \in S$ מתקיים:      $L_{S}\notin RE$

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

משפט: בהנתן תכונה $S\subseteq RE$, אז $L_{S}\in RE$ אם"ם מתקיימות כלל התכונות הבאות: עבור שתי שפות $L,L'\in RE$, אם $L'\in S$ וגם $L'\subseteq L$, אז $L\in S$. אם $L\in S$, אז יש ל־$L$ תת־שפה סופית $L'\subseteq L$ המקיימת $L'\in S$. קיימת מ״ט המונה כל שפה סופית ב־$S$.

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

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

הוכחה: להלן תיאור מכונה $Q$ המקבלת קידוד של מ״ט $M$, ובהכרח עוצרת בתשובה חיובית אם $L(M)\in S$, ולעולם לא עוצרת בתשובה חיובית אם $L(M)\notin S$. הרעיון הכללי הוא להשתמש ב"הרצה במקביל" (dovetailing) (טכניקה שכבר ראינו במודל לבעיות הכרעה).

נשים לב שמתנאי 3 נובע שישנה מכונה $Q_{3}$ אשר בהנתן שפה סופית השייכת ל־$S$, עוצרת בשלב כלשהו ומקבלת את השפה. המכונה $Q$ משתמשת ב$Q_{3}$.

המכונה $Q$ פועלת במספר לולאות מקוננות:

1. בלולאה החיצונית ביותר, היא מקדמת אינדקס $i=0,1,2,\ldots$. עבור כל $i$, היא מייצרת את המחרוזת ה-$i$ בסדר לקסיקורפי.
2. בלולאה פנימית יותר, עבור ערך $i$ והמחרוזת ה-$i$, היא מפעילה את $M$ למשך $i$ שלבים. אם המילה מתקבלת, $Q$ מוסיפה אותה לרשימת מילים ש-$M$ מקבלת.
3. בלולאה פנימית יותר, עבור רשימת המילים שהתקבלו ע"י $M$ עד כה, המכונה $Q$ מייצרת את כל תת-הקבוצות האפשריות של המילים שהתקבלו עד כה.
4. בלולאה הפנימית ביותר, עבור ערך $i$ ותת-קבוצה של מילים מתקבלות, המכונה $Q$ מריצה את $Q_{3}$ לשאול האם תת-הקבוצה שייכת ל$S$. אם כן, המכונה $Q$ עוצרת בתשובה חיובית.

נשים לב שמתכונה 1 נובע שאם $L=L(M)\in S$, אז יש לה תת-שפה סופית $L'$ שגם היא ב-$S$. שיטת הdovetailing כאן מבטיחה שהחל משלב כלשהו, $L'$ תשקל על ידי $Q_{3}$. תנאי 3 מבטיח שבזמן סופי כלשהו, $Q_{3}$ תזהה את $L'$ כשייכת ל-$S$. שוב פעם, שיטת הdovetailing מבטיחה שלאחר מספיק איטרציות $Q_{3}$ תפעל מספיק פעמים על $L'$. כלומר, אם התשובה חיובית, אז $Q$ בוודאות תחזיר תשובה חיובית.

נותר להראות ש-$Q$ לא תחזיר תשובה חיובית במקרה שאיננו נכון. אך נשים לב שזה בדיוק מה שתנאי 1 אומר שאינו קורה: השפה $L'$ היא תת-שפה של $L=L(M)$, עפ"י בניה. היא שייכת ל-$S$ עפ"י תנאי 3 והעובדה ש$Q_{3}$ זיהתה אותה. השפה $L$ נתנת למניה רקורסיבית (שהרי זו שפה של מ״ט). מכאן נובע ש-$L$ גם היא ב-$S$.

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

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

הפרק הקודם: רדוקציה חישובית

משפט רייס תרגילים

הפרק הבא: אי-הפרדתיות רקורסיבית