לדלג לתוכן

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

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

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

[עריכה]

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


הפתרון

נראה רדוקציה .

נגדיר פונקציה , כאשר המכונה על הקלט w מבצעת כלהלן:

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

(הערה: אם הקלט של הפונקציה f אינו חוקי, פלט הפונקציה יהיה הקידוד של מכונה שמקבלת כל קלט; לפי הגדרתנו, מחרוזת לא חוקית היא קידוד של מכונה שישר דוחה. מכונה כזו שייכת ל־HP ולכן הפלט המומר נדרש להיות ב־ על־מנת שלא לפגום בתקפות הרדוקציה).


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

  1. זו פונקציה מלאה, המוגדרת לכל קלט.
  2. f ברת חישוב: קיימת מ״ט שממירה את המחרוזת למחרוזת המתאימה . הקידוד של מכונת הפלט מכיל
    1. 2 מעברים המבצעים מחיקה של הקלט (w).
    2. מעברים המבצעים כתיבה של x על הסרט (שים לב: x היא מילה נתונה! פעולה זו ניתנת לביצוע ע״י מעברים)
    3. פונקציית המעברים של , אולי תוך שינוי אינדקסים (נדרשים מעברים, בהתאם למכונה M)
    4. מעבר ל־ אם M הגיעה למצב סופי שלה (מעבר 1 נוסף)
    • כל הפעולות הנ״ל סופיות ומוגדרות היטב עבור קלט נתון, ועל־כן קל לבצעם באופן "אוטומטי" בעזרת מ״ט.
  3. f תקפה. נבחן מהי השפה של המכונה :
    • נניח ש־M לא עוצרת על x. המכונה תכנס ללולאה בשלב בו היא מריצה את M על x, ולא תקבל את הקלט שלה, עבור כל קלט w. במקרה זה, .
    • נניח ש־M עוצרת על x. המכונה , לפי הגדרתה מקבלת את הקלט w, בלי קשר לתוכנו, כלומר במקרה זה .
    • מהאמור לעיל מתקבלת התקפות: אם אז M עוצרת על x   ←     ←   . המקרה השני זהה.

מתקיים וממשפט הרדוקציה (ההפכי) נובע שבגלל ש־ גם , כנדרש.


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

[עריכה]

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

הפתרון

רמז: ע״י הרדוקציה .


רמז 2: פונקציית הרדוקציה
, כאשר  היא מכונה קבועה שתמיד מקבלת את הקלט במעבר הראשון.


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

[עריכה]

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

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

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

[עריכה]

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

.

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

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


הפתרון

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

  1. נקרא לפונקציה , ונשמור את התוצאה ב.
  2. אם , נחליט ש אינה עוצרת על המחרוזת הריקה.
  3. אחרת, נסמלץ את ריצת על המחרוזת הריקה לכל היותר צעדים. נחזיר האם היא עצרה.

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


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

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

[עריכה]

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

הפתרון

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


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

[עריכה]

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


הפתרון

ראשית נבנה מניה עבור כל מ"ט. עבור , נניח ש- היא מ"ט מספר במניה.

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

נגדיר את המכונה כמכונה המריצה קודם את , ואם היא דוחה, מריצה את .

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

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

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

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

כדי להראות ש איננה רקורסיבית, אפשר לראות שאם היינו מניחים בשלילה שהיא כן, היה אפשר לפתור את בעיית העצירה. בהנתן מ"ט כלשהי וקלט , נמנה את כל השלשות (i, j, k) עד שנזהה שלשה כלשהי שעבורה

ונשאל האם .