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

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

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

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

נגדיר $L_{\mathrm{\varnothing }}=\{⟨M⟩\mid L(M)=\mathrm{\varnothing }\}$ מהי התכונה המתאימה למשפט רייס? האם השפה רקורסיבית? תבנית:מוסתר

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

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

$L=\{⟨M⟩\mid M\text{ visits each state in }Q\setminus F\}$

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

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

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

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

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

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

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

אם $L^{\prime }\in S$, וכן $L,L^{\prime }\in RE$, וכן $L^{\prime }\subseteq L$, אז $L\in S$

אז $L_S\notin RE$.

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

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

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

אם במהלך השלב הראשון $M^{\prime }$ מקבלת את $w$, המכונה תחזיר תשובה חיובית. אחרת, היא תמשיך לשלב השני.

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

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

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

אם $L\in S,$, אז יש ל-$L$ תת-שפה סופית $L^{\prime }\subseteq L$ המקיימת $L^{\prime }\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-יות

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