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

אופטימיזציית מ"ט

בהנתן מ"ט $M$ הפועלת על מחרוזות, ברצוננו לדעת האם אפשר לבצע אופטימיזציה ולייצר מכונה שמקבלת את אותה שפה, כך שזמן ריצתה יהיה קטן מ־$|x|$, אורך הקלט שלה. האם זו בעיה כריעה?

הפתרון

כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה

$S_{P}=\{L|L\in RE\bigwedge \exists _{M}\forall _{x}M{\text{accepts }}x{\text{ in less than}}|x|{\text{ steps}}\}.$

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

• היא מכילה לפחות שפה אחת: את השפה $\Sigma ^{*}$ אפשר לזהות בעזרת מ״ט המקבלת כל קלט בצעד יחיד.
• היא חסרה לפחות שפה אחת: נניח שפה מהצורה $L=\{wb\mid w=w_{1}w_{2}\ldots w_{k}\in \Sigma ^{*},b\in \Sigma ,\exists i\ w_{i}=b\}$, כאשר $b$ הוא תו כלשהו ו-$w$ היא מחרוזת שאחת מהאותיות בה נדרשת להיות $b$. קל לראות שכל מ״ט המקבלת את השפה חייבת לקרוא את הקלט עד סופו, ולכן זמן ריצתה הוא לכל הפחות $|x|$, ועל כן $L\notin S_{P}$.

לפי משפט רייס, בעיית ההכרעה של השפה $L_{S_{P}}$ אינה ב־$R$, ובפרט, לא ניתן להכריע את השאלה האם ניתן לבצע אופטימיזציה כזו.

זיהוי שפה ריקה

נגדיר $L_{\emptyset }=\{\langle M\rangle \mid L(M)=\emptyset \}$ מהי התכונה המתאימה למשפט רייס? האם השפה רקורסיבית?

הפתרון

נגדיר את התכונה $S=\{\emptyset \}$, מכילה שפה אחת ולכן אינה טריוויאלית, ולפי המשפט $L_{\emptyset }\notin R$.

מ״ט המבקרת בכל המצבים

בהנתן מ"ט $M$ ומחרוזת $x$, ברצוננו לדעת האם $M$ עוברת בכל אחד ממצביה הלא־סופיים,

$L=\{\langle M\rangle \mid M{\text{ visits each state in }}Q\smallsetminus F\}$

האם ניתן להשתמש במשפט רייס כדי לטעון שהבעיה איננה כריעה באופן כללי? אם כן, נמק. אם לא, הסבר היכן קורסת ההוכחה.

אופטימיזציית מ"ט

בהנתן מ"ט $M$ הפועלת על מחרוזות, ברצוננו לדעת האם אפשר לטייב אותה כך שזמן ריצתה יהיה פולינומי ב-$|x|$, כלומר אורך הקלט שלה. האם זו בעיה כריעה?

הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית

הוכח את המשפט הבא:

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

הפתרון

בהוכחת משפט רייס ראינו רדוקציה ${\text{HP}}\leq L_{S}$. קל לראות שעבור התכונה המשלימה מתקיים $L_{\overline {S}}={\overline {L_{S}}}$.
מאלה נובע בסופו של דבר ש־${\overline {\text{HP}}}\leq L_{S}$ ומכאן ש־$L_{S}\notin RE$ (משפט הרדוקציה ההפכי)

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

הראה את הכרחיות התנאי הראשון להיות החלטת תכונה ב-$RE$. דהיינו, הראה שאם התנאי הבא אינו מתקיים:

אם $L'\in S$, וכן $L,L'\in RE$, וכן $L'\subseteq L$, אז $L\in S$

אז $L_{S}\notin RE$.

הנחיה: הראה שאם התנאי אינו מתקיים, אך $L_{S}\notin RE$, אז אפשר לכל מ"ט $M$ ומחרוזת $x$ להכריע האם $M$ מקבלת את $x$ (כלומר, להכריע את בעיית העצירה).

נניח ש-$M'$ ו-$M$ הן המ"ט של $L'$ ו$L$, בהתאמה. בנה את המכונה הבאה $Q$. בהנתן קלט $w$, המכונה פועלת בשני שלבים. בשלב הראשון, המכונה מריצה "במקביל" את $M$ על $x$ ואת $L'$ על $w$:

1. בלולאה, היא מריצה מונה $i=0,1,2,\ldots$
2. עבור כל אינדקס $i$, היא מריצה $i$ צעדים של $M$ ו-$i$ צעדים של $M'$.

אם במהלך השלב הראשון $M'$ מקבלת את $w$, המכונה תחזיר תשובה חיובית. אחרת, היא תמשיך לשלב השני.

בשלב השני, המכונה מריצה את $M$ על $w$, ומחזירה את תשובתה.

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

הראה את הכרחיות התנאי השני להיות החלטת תכונה ב-$RE$. דהיינו, הראה שאם התנאי הבא אינו מתקיים:

אם $L\in S,$, אז יש ל-$L$ תת-שפה סופית $L'\subseteq L$ המקיימת $L'\in S$

אז $L_{S}\notin RE$.

הנחיה: הראה שאם התנאי אינו מתקיים, אך $L_{S}\notin RE$, אז אפשר לכל מ"ט $M$ ומחרוזת $x$ להכריע האם $M$ מקבלת את $x$ (כלומר, להכריע את בעיית העצירה).

נניח ש-$M_{L}$ היא מ"ט של $L$, בהתאמה. בנה את המכונה הבאה, $Q$. בהנתן קלט $w$, המכונה פועלת בשני שלבים. בשלב הראשון, המכונה $Q$ מריצה את $M$ על $x$ במשך $|w|$ שלבים. אם במהלך שלב זה $M$ קיבלה את $x$, אז המכונה $Q$ תחזיר תשובה שלילית. אחרת היא תמשיך לשלב השני.

בשלב השני, המכונה $Q$ מריצה את $M_{L}$ על $w$, ומחזירה את תשובתה.

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

הראה את הכרחיות התנאי השלישי להיות החלטת תכונה ב-$RE$. דהיינו, הראה שאם התנאי הבא אינו מתקיים:

שפת כל השפות הסופיות ב-$S$ היא ב-$RE$ (כלומר, יש מ"ט המונה כל שפה סופית ב-$S$).

אז $L_{S}\notin RE$.

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

הרחבת משפט רייס לn-יות

הגדרה: תכונה של $n$-יית שפות ב-$RE$ היא קבוצה $S$ של שפות נתנות למניה רקורסיבית מהצורה $(L_{1},\ldots ,L_{n})$. נגיד שתכונה $S$ איננה טריוויאלית אם קיימות שתי $n$-יות כך ש-$(L_{1},\ldots ,L_{n})\in S$ ו-$(L'_{1},\ldots ,L'_{n})\notin S$.

1. הוכח ש$L_{S}\notin R$.
2. הראה שבעיית ההחלטה האם שתי מ"ט מקבלות אותה שפה - איננה כריעה.