תורת החישוביות/כריעות שפות/שפות שאינן כריעות/תרגילים

כריעות שפות הכוללות את כל המחרוזות

הראה שהשפה $L_{\Sigma ^{*}}=\{\langle M\rangle \mid L(M)=\Sigma ^{*}\}$, אינה כריעה.

הפתרון

נראה רדוקציה ${\text{HP}}\leq L_{\Sigma ^{*}}$.

נגדיר פונקציה $f(\langle M\rangle ,x)=\langle M_{x}\rangle$, כאשר המכונה $M_{x}$ על הקלט w מבצעת כלהלן:

1. מוחקת את w מסרט הזיכרון
2. מריצה את M על x
3. אם M עצרה על x, $M_{X}$ מקבלת (את הקלט w).

(הערה: אם הקלט של הפונקציה f אינו חוקי, פלט הפונקציה יהיה הקידוד $\langle M_{0}\rangle$ של מכונה שמקבלת כל קלט; לפי הגדרתנו, מחרוזת לא חוקית היא קידוד של מכונה שישר דוחה. מכונה כזו שייכת ל־HP ולכן הפלט המומר נדרש להיות ב־$L_{\Sigma ^{*}}$ על־מנת שלא לפגום בתקפות הרדוקציה).

נוכיח שפונקציה זו היא אכן רדוקציה:

1. זו פונקציה מלאה, המוגדרת לכל קלט.
2. f ברת חישוב: קיימת מ״ט שממירה את המחרוזת $(\langle M\rangle ,x)$ למחרוזת המתאימה $\langle M_{x}\rangle$. הקידוד של מכונת הפלט מכיל
   1. 2 מעברים המבצעים מחיקה של הקלט (w).
   2. מעברים המבצעים כתיבה של x על הסרט (שים לב: x היא מילה נתונה! פעולה זו ניתנת לביצוע ע״י $|x|$ מעברים)
   3. פונקציית המעברים של $M$, אולי תוך שינוי אינדקסים (נדרשים $|Q|$ מעברים, בהתאם למכונה M)
   4. מעבר ל־$q_{acc}$ אם M הגיעה למצב סופי שלה (מעבר 1 נוסף)
   • כל הפעולות הנ״ל סופיות ומוגדרות היטב עבור קלט $(\langle M\rangle ,x)$ נתון, ועל־כן קל לבצעם באופן "אוטומטי" בעזרת מ״ט.
3. f תקפה. נבחן מהי השפה של המכונה $M_{x}$:
   • נניח ש־M לא עוצרת על x. המכונה $M_{x}$ תכנס ללולאה בשלב בו היא מריצה את M על x, ולא תקבל את הקלט שלה, עבור כל קלט w. במקרה זה, $L(M_{x})=\emptyset$.
   • נניח ש־M עוצרת על x. המכונה $M_{x}$, לפי הגדרתה מקבלת את הקלט w, בלי קשר לתוכנו, כלומר במקרה זה $L(M_{x})=\Sigma ^{*}$.
   • מהאמור לעיל מתקבלת התקפות: אם $(\langle M\rangle ,x)\in {\text{HP}}$ אז M עוצרת על x   ←  $L(M_{x})=\Sigma ^{*}$   ←   $\langle M_{x}\rangle \in L_{\Sigma ^{*}}$. המקרה השני זהה.

מתקיים ${\text{HP}}\leq L_{\Sigma ^{*}}$ וממשפט הרדוקציה (ההפכי) נובע שבגלל ש־$HP\notin R$ גם $L_{\Sigma ^{*}}\notin R$, כנדרש.

כריעות שוויון בין שפות הנוצרות ע"י מ"ט שונות

הראה שהשפה $L_{eq}=\{\langle M_{1}\rangle ,\langle M_{2}\rangle \mid L(M_{1})=L(M_{2})\}$ אינה כריעה.

הפתרון

רמז: ע״י הרדוקציה $L_{\Sigma ^{*}}\leq L_{eq}$.

רמז 2: פונקציית הרדוקציה

$f(\langle M\rangle )=\langle M\rangle \langle M_{0}\rangle$, כאשר $M_{0}$ היא מכונה קבועה שתמיד מקבלת את הקלט במעבר הראשון.

אתגר: הבונה העסוק

נגדיר את פונקציית "הבונה העסוק (וק')": $BB(n)$ בתור מספר הצעדים המקסימלי שמבצעת מ״ט עם לכל היותר n מצבים על הקלט הריק $\varepsilon$, בהנחה שהמ״ט עוצרת.

1. הוכח כי הפונקציה $BB(n)$ אינה ברת־חישוב. במילים אחרות, לא קיימת מ״ט אשר עבור קלט n מחשבת את $BB(n)$.
2. נגדיר את הקבוע c בתור הסכום האינסופי $c={\frac {1}{BB(1)}}+{\frac {1}{BB(2)}}+{\frac {1}{BB(3)}}+\ldots$. הפונק' $BB()$ גדלה הרבה יותר מהר מאשר, למשל, $x^{2}$, ולכן הטור מתכנס. האם המספר c הוא מספר חשיב (וק')? כלומר, האם קיימת מ״ט אשר על קלט $1^{n}$ (n פעמים הספרה '1') רושמת על סרט הפלט את n הספרות הראשות של c ?

פונקציה לחישוב המ"ט שייצוגה מקסימלית תחת חסם מספר צעדים

נגדיר את הפונקציה $f$ בצורה הבאה. בהנתן המחרוזת הריקה $\epsilon$, אם מ"ט $M$ עוצרת עליה, אז $f(\langle M\rangle )$ היא מספר הצעדים עד העצירה. אחרת, $f(\langle M\rangle )=0$. נגדיר את הפונקציה $g$ כך:

$g(y)=\max _{\langle M\rangle \leq y}f(\langle M\rangle )$

.

(הנח שאפשר להתייחס ל $\langle M\rangle$ כמספר).

הראה ש$g$ איננה נתנת לחישוב.

הפתרון

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

1. נקרא לפונקציה $g(\langle M\rangle )$, ונשמור את התוצאה ב$s$.
2. אם $s=0$, נחליט ש$M$ אינה עוצרת על המחרוזת הריקה.
3. אחרת, נסמלץ את ריצת $M$ על המחרוזת הריקה לכל היותר $s$ צעדים. נחזיר האם היא עצרה.

נשים לב שאם $M$ עוצרת על המחרוזת הריקה, אז היא בהכרח עושה זאת תוך $s$ צעדים.

הראה שלכל פונקציה נתנת לחישוב $h$, $g$ גדלה מהר יותר מ$h$.

הכרעה בעצירת מ"ט תוך שימוש במספר חסום של תאים

האם אפשר לכתוב פונקציה נתנת לחישוב אשר מקבלת קידוד מ"ט $\langle M\rangle$, מחרוזת $x$, ומספר שלם $k$, ומוצאת האם היא מקבלת את המחרוזת תוך שימוש ב$k$ תאים מהסרט?

הפתרון

רמז: חשוב על מספר הקונפיגורציות האפשריות של המכונה.

בעיית זוגות בלתי כריעה בעלת קומפוננטות כריעות

מצא שפה $B\in RE\setminus R$ של זוגות מספרים טבעיים, כך שמתקיים $\{x|(x,y)\in B\}\in R$ וכן $\{y|(x,y)\in B\}\in R$.

הפתרון

ראשית נבנה מניה עבור כל מ"ט. עבור $i=0,1,2,\ldots$, נניח ש-$M_{i}$ היא מ"ט מספר $i$ במניה.

נגדיר את $M'_{j}$ כמכונת טיורינג בעלת מבנה ספיציפי כלשהו, בו נקבע שאם המכונה מקבלת כקלט את המספר $j$ היא מקבלת, ואחרת היא דוחה). (שים לב ש$M'_{j}$ אינו סימון למכונה כלשהי המקבלת אך ורק את $j$, אלא מכונה בעלת מבנה ספיציפי העושה זאת).

נגדיר את המכונה $M''_{j,i}$ כמכונה המריצה קודם את $M'_{j}$, ואם היא דוחה, מריצה את $M_{i}$.

נגדיר כעת את הקבוצה $B$:

$B=\{(\langle M''_{j,i}\rangle ,k)|M''_{j,i}{\text{ halts on }}k\}.$

(כאשר הכוונה היא ש-$k$ היא מחרוזת כלשהי שמתייחסים אליה כמספר).

קל לראות שהקבוצה $\{x|(x,y)\in B\}\in R$ ב-$R$: בהנתן $x$, יש לבדוק האם מדובר בשרשור של מכונה $M'_{j}$ עם מ"ט חוקית כלשהי. עוד יותר קל לראות שהקבוצה $\{y|(x,y)\in B\}\in R$: כל מחרוזת שייכת לקבוצה זו.

לא קשה גם לראות שהקבוצה $B$ נתנת למניה רקורסיבית.

כדי להראות ש$B$ איננה רקורסיבית, אפשר לראות שאם היינו מניחים בשלילה שהיא כן, היה אפשר לפתור את בעיית העצירה. בהנתן מ"ט $M$ כלשהי וקלט $x$, נמנה את כל השלשות (i, j, k) עד שנזהה שלשה כלשהי שעבורה $k=x$ $\langle M_{i}\rangle =\langle M\rangle$ $j\neq x$

ונשאל האם $(\langle M''_{j,i}\rangle ,k)\in B$.