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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

הראה שהשפה , אינה כריעה.



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

הראה שהשפה אינה כריעה.


אתגר: הבונה העסוק[עריכה]

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

  1. הוכח כי הפונקציה אינה ברת־חישוב. במילים אחרות, לא קיימת מ״ט אשר עבור קלט n מחשבת את .
  2. נגדיר את הקבוע c בתור הסכום האינסופי
    .
    הפונק' גדלה הרבה יותר מהר מאשר, למשל, , ולכן הטור מתכנס. האם המספר c הוא מספר חשיב (וק')? כלומר, האם קיימת מ״ט אשר על קלט (n פעמים הספרה '1') רושמת על סרט הפלט את n הספרות הראשות של c ?

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

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

.

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

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



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

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

האם אפשר לכתוב פונקציה נתנת לחישוב אשר מקבלת קידוד מ"ט , מחרוזת , ומספר שלם , ומוצאת האם היא מקבלת את המחרוזת תוך שימוש ב תאים מהסרט?


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

מצא שפה של זוגות מספרים טבעיים, כך שמתקיים וכן .