משתמש:חישוביות/HW2

תורת החישוביות – 236343 – תרגיל בית 2

שאלה 1

1. $f(\sigma )=\epsilon$
   ברור שהפונקציה מלאה (לכל ערך הארגומנט ערכה מוגדר) וניתנת לחישוב (על ידי מ"ט עם מצב יחיד בלבד שהוא סופי).
2. $f(\langle M\rangle )={\begin{cases}''{\text{YES}}'',&M\ {\text{halts on every input}}\\''{\text{NO}}'',&M\ {\text{doesn}}'{\text{t halt on some input,}}\\&{\text{or}}\ \langle M\rangle \ {\text{doesn}}'{\text{t represent a valid TM}}\end{cases}}$
   הפונקציה מלאה, כי לכל קידוד מוגדר האם הוא תואם למ"ט חוקית, ואם כן, מוגדר האם היא עוצרת בהנתן קלט ריק $\epsilon$, אך בהרצאות הוכחנו שהפונקציה הזאת לא ניתנת לחישוב.
3. נבנה מ"ט $M$ שעוצרת מיד במצב התחילתי, אם הקלט ריק, ונכנסת מיד ללולאה אינסופית, אם הוא לא. (זה יקח לנו שני מצבים, ואחד מהם סופי.)
   $f_{M}(\sigma )=\epsilon ,\ {\text{if}}\ \sigma =\epsilon ,$ וערך הפונקציה לא מוגדר ל-$\sigma \not =\epsilon$.
   מקיום המכונה נובע שהפונקציה ניתנת לחישוב, אך היא אינה מלאה.
4. $f(\langle M\rangle )={\begin{cases}''{\text{YES}}'',&M\ {\text{halts on every input}}\\''{\text{NO}}'',&M\ {\text{doesn}}'{\text{t halt on some input,}}\\{\text{undefined}},&\langle M\rangle \ {\text{doesn}}'{\text{t represent a valid TM}}\end{cases}}$
   הפונקציה לא מלאה, כי ערכה לא מוגדר למחרוזות שאינן קידודים חוקיים של מכונות, ובנוסף לכך היא לא ניתנת לחישוב, כי אף למכונות חוקיות אי אפשר לבנות מ"ט שתענה האם המכונה הנתונה תעצור.

שאלה 2

1. $L=\emptyset$, כי מקיום $M$ נובע ש-$f_{M}$ ניתנת לחישוב. עם זאת, $L'\not =\emptyset$, למשל $\langle M_{STAM}\rangle \in L'$, כש-$M_{STAM}$ היא המכונה עם מצב אחד לא סופי שמיד נכנסת ללולאה אינסופית ולא עוצרת על שום קלט. בכך הוכחנו ש-$L\subset L'$.
2. $M$ מקבלת את $L(M)$, אז $L(M)\in RE$. אם ורק אם גם ${\overline {L(M)}}\in RE\leftrightarrow L(M)\in CoRE$, אז $L(M)\in RE\cap CoRE=R$. בכך הוכחנו ש-${\overline {L(M)}}\in RE\leftrightarrow L(M)\in R,L=L'$.
3. אם $M$ עוצרת על כל קלט, אז היא מכריעה את $L(M)$, ומקיום מכונה המכריעה את השפה נובע ש-$L(M)\in R$. לעומת זאת, מזה ש-$L(M)\in R$ לא נובע ש-$M$ מכריעה את $L(M)$, למשל היא יכולה להיכנס ללולאה אינסופית במקום דחיית הקלט ואף פעל לא לעצור במצב הדוחה. זה אומר ש-$L'\subset L$.
4. $\exists M\in L\setminus L'$: $M$ מקבלת את $\epsilon$ ודוחה כל קלט לא ריק, היא תמיד עוצרת אחרי צעד אחד למרות שהשפה $L(M)=\{\epsilon \}$ היא סופית.
   $\exists M\in L'\setminus L$: $M$ מקבלת את השפה $\{a\}^{*}$ ונכנסת ללולאה אינסופית מכל קלט המכיל אות אחרת. (זה יקח לנו שני מצבים, ואחד מהם סופי.) קיימת שפה אינסופית $\Sigma ^{*}\setminus \{a\}^{*}$ שעל הקלטים ממנה $M$ אינה עוצרת, אבל גם השפה שאותה המכונה מקבלת היא אינסופית.
   בכך הוכחנו שבין שתי השפות אין יחס הכלה.

שאלה 3

$L(M_{1})$ היא שפה מסוימת, אז $n\triangleq |L(M_{1})|,n\in (\mathbb {N} \cup \{\infty \})$ זה ערך קבוע. $L={\Big \{}x{\Big |}|x|<n{\Big \}}$

מקרה א) $n=\infty ,L={\Big \{}x{\Big |}|x|<\infty {\Big \}}=\Sigma ^{*}\in R$ (כי המכונה שמיד עוצרת ומקבלת מכריעה את השפה $\Sigma ^{*}$)

מקרה ב) $n<\infty ,L=\textstyle \bigcup _{i=0}^{n-1}\Sigma ^{i}\in R$ (כי המכונה שעושה $n$ צעדים ימינה, מקבלת אם היא רואה תא ריק, ודוחה אם התא לא ריק, – מכריעה את השפה $L$)

בשני המקרים, $L\in R$

שאלה 4

1. $L_{1}=\{\langle M\rangle |\langle M\rangle \in L(M_{0})\}=\{x|x\in L(M_{0})\}=L(M_{0})\in R$ (משום ש-$M_{0}$ עוצרת תמיד, היא מכריעה את $L(M_{0})$.)
2. $x\triangleq \langle M_{0}\rangle$ היא מחרוזת מסוימת, אז $L_{2}=\{\langle M\rangle |x\in L(M)\}\in RE$ (נבנה מכונה שבהנתן קידוד $\langle M\rangle$ מריצה את $M$ על $x$. אם $M$ מקבלת את $x$, אז היא תעצור, ולכן גם המכונה שלנו תעצור.) עם זאת, $L_{2}\not \in R$ לפי משפט רייס (שייכות מילה לשפה הינה תכונה לא טריויאלית, לדוגמה השפות הסופיות $\emptyset$ ו-$\{x\}$ מדגימות שפות מ-$R$ בעלת וחסרת התכונה.)

שאלה 5

1. קודם כל, תוך 1000 צעדים המכונה יכולה להספיק להסתכל ב-1000 תאים לכל היותר, כלומר היא מקבלת או דוחה קלט על סמך 1000 האותיות הראשונות שלו בלבד. אז אם בכלל קיים קלט עליו המכונה עוצרת תוך 1000 צעדים, אזי קיימת בפרט מילה (הרישא שלו) באורך 1000 או פחות שעליה המכונה עוצרת גם כן תוך 1000 צעדים. מזה נובע ש-$L_{1}\in R$: נבנה מכונה שבהנתן $\langle M\rangle$ מריצה את $M$ על כל מילה בסדר הלקסיקוגרפי בתורות, עד שתעצור, או לכל היותר 1000 צעדים; המכונה מקבלת את $\langle M\rangle$ אם $M$ עצרה על הקלט שלה תוך 1000 הצעדים, ואחרת ממשיכה לקלט הבא בסדר הלקסיקוגרפי. אחרי המילה בת 1000 אותיות האחרונה המכונה שלנו עוצרת ודוחה. בכך, אם קיים קלט קצר מ-1000 (מספר $k$ בסדר הלקסיקוגרפי) שעליו M עוצרת תוך 1000 צעדים, אז גם המכונה שבנינו תעצור תוך $1000\cdot k$ צעדים לכל היותר, ותקבל; ואילו אם קלט כזה אינו קיים (ולפי הטיעון שלנו זה אומר שאין בכלל קלט עליו $M$ עוצרת תוך 1000 צעדים), אז המכונה שבנינו תעצור ותדחה אחרי $1000\cdot (1+|\Sigma |+...+|\Sigma |^{1000})=1000\cdot {\frac {|\Sigma |^{1001}-1}{|\Sigma |-1}}$ צעדים לכל היותר. קיום מכונה המכריעה את השפה $L_{1}$ מוכיח את השייכות $L_{1}\in R$.
2. $L_{2}\in RE$: נבנה מכונה שבהנתן $\langle M\rangle$ מריצה את $M$ על כל מילה באורך קטן מ-100 במקביל (מספר המלים האלה מסוים ושווה $1+|\Sigma |+...+|\Sigma |^{99}={\frac {|\Sigma |^{100}-1}{|\Sigma |-1}}$), ועוצרת כשאחד מהתהליכים מקבל את המילה. המכונה שלנו תקבל את $L_{2}$. עם זאת, $L_{2}\not \in R$ לפי משפט רייס: ישנן שפות סופיות המכילות מלים קטנות מ-100 (למשל $\{\epsilon \}$) וגם שפות סופיות שלא מכילות כזה מלים (למשל $\emptyset$).

שאלה 6

1. הפרכה: נקח $M$ עם שני מצבים שאחד מהם סופי, שמיד מקבלת קלט ריק ולכל קלט אחר מיד נכנסת ללולאה אינסופית. שפתה $L(M)=\{\epsilon \}$. המכונה ${\overline {M}}$ מיד תדחה קלט ריק ולכל קלט אחר מיד תיכנס ללולאה אינסופית, לכן שפתה תהיה $L({\overline {M}})=\emptyset$. שתי השפות אינן משלימות: ${\overline {\emptyset }}=\Sigma ^{*}\not =\{\epsilon \}$.
2. הפרכה: נקח $M_{1}$ שבנינו בסעיף הקודם, ו$M_{2}$ עם שלושה מצבים ששניהם סופיים: היא מיד מקבלת קלט ריק, ומיד דוחה כל קלט אחר. ברור ש-$L(M_{2})=L(M_{1})=\{\epsilon \}$ והראנו ש-$L({\overline {M_{1}}})=\emptyset$; עם זאת, המכונה ${\overline {M_{2}}}$ מיד דוחה קלט ריק ומיד מקבלת כל קלט אחר, לכן שפתה $L({\overline {M_{2}}})=(\Sigma ^{*}\setminus \{\epsilon \})={\overline {L(M_{2})}}\not =L({\overline {M_{1}}})=\emptyset$.
3. הפרכה: נקח $M$ שבהנתן קידוד מכונה $\langle M_{1}\rangle$ מריצה אותה על קלט ריק, וכשהסימולציה מסתיימת (כלומר $M_{1}$ עוצרת על קלט ריק), $M$ דוחה. משום ש-$M$ אף פעם לא מקבלת, שפתה ריקה: $L(M)=\emptyset \in R$, אבל ${\overline {M}}$ מקבלת את השפה $L_{\epsilon }$ שעבורה הוכחנו בכיתה ש-$L({\overline {M}})=L_{\epsilon }\in (RE\setminus R)$. (מפני שהשייכות $\epsilon \in L(M_{1})$ מהווה תכונה לא טריויאלית של שפה, אז לפי משפט רייס $L_{\epsilon }=\{\langle M_{1}\rangle |\epsilon \in L(M_{1})\}\not \in R$)