» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
שאלות חזרה
דף ראשי  מכונת טיורינג  שאלות חזרה גרסה להדפסה

      שאלות חזרה

 

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

 

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

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

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

 

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

 

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

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

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

 

 28-01-04 / 12:02  עודכן ,  25-01-04 / 11:15  נוצר ע"י שמרית דויטש  בתאריך 
 מכונת טיורינג למנייה - הקודםהבא - שאלות חזרה- המשך 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 3