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

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

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

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

הראה שהשפה $L_{eq}=\{⟨M_1⟩,⟨M_2⟩\mid L(M_1)=L(M_2)\}$ אינה כריעה. תבנית:מוסתר

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

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

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

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

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

$g(y)=\underset{⟨M⟩\le y}{\max }f(⟨M⟩)$

.

(הנח שאפשר להתייחס ל $⟨M⟩$ כמספר).

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

תבנית:מוסתר

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

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

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

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

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