שאלות חזרה

 נסמן ב-A את אוסף השפות הניתנות לקבלה, וב-B את אוסף השפות הניתנות להכרעה. נניחשנתון לנו כי B מוכל ממש ב-A . הוכיחו כי A אינה סגורה תחת המשלים, כלומר A^C≠A.

פתרון: נניח כי אוסף השפות הניתנות לקבלה סגור תחת השלמה, ותהי L שפה ניתנת לקבלה. אזי גם L^C ניתנת לקבלה. תהיינה M ו-M' מ"ט המקבלות אותן בהתאמה. נבנה מ"ט M_L להכרעת L : לכל קלט w, M_L מריצה את M ואת M' על w צעד צעד לסירוגין. ברור כי אחת בלבד מן האפשרויות מתקיימת, ז"א w שייכת לאחת מן השפות בלבד, לכן M או M' תעצור על w, ובהתאם M_L תכריע אם w שייכת ל-L או לא.

קיבלנו כי L שפה ניתנת להכרעה, כלומר ניתנת לקבלה גוררת ניתנת להכרעה. ידוע לנו כי ההיפך הוא הנכון- ניתנת להכרעה גוררת ניתנת לקבלה. לכן, שתי משפחות השפות- הכריעות והניתנות לקבלה- זהות, בסתירה לנתון.

מכאן שאוסף השפות הניתנות לקבלה לא סגור תחת פעולת ההשלמה.

 תהי  1 Lשפה הניתנת להכרעה. הוכיחו כי גם L^C ניתנת להכרעה.

פתרון: תהי MC מ"ט העובדת על סרט אחד, עם קונפיגורציה התחלתית (s,#,w, #) לכל wε{Σ-{#}}* , אשר פעולתה מוגדרת באופן הבא:

1)       הפעלת M1 על הסרט

2)       אם התוצאה שהחזירה M1 היא ## - כתיבה של המחרוזת #1# בקצה השמאלי של הסרט ועצירה. אחרת, M1 החזירה #1# - מתבצעת החלפה של ה-1 ב-# ועצירה.