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

משפט השקילות

 

משפט: תהי L שפה. L ניתנת לקבלה ע"י מכונת טיורינג לא דטרמינסטית אם ורק אם L ניתנת לקבלה ע"י מכונת טיורינג דטרמינסטית.

הוכחה: כל מ"ט דטרמיניסטית היא סוג של יחס של לא דטרמיניסטית, לכן צד אחד טריויאלי.

נוכיח את הצד השני:

הרעיון: בהינתן מ"ט לא דטרמיניסטית A=(QA, ∑A,∆A,sA,hA) נבנה מ"ט דטרמיניסטית

 B=(QB, ∑B,δ B,sB,hB)  שמבצעת סימולציה למכונה A , ומנסה את כל האפשרויות למעברים הלא דטרמיניסטית (כשיש).

נסתכל על הקבוצה P=(QA× (∑AU{R,L}))* זוהי קבוצה של זוגות, כאשר כל זוג מכיל מצב ופעולה.

נגדיר סדר על הזוגות האלו:

עבור p1, p2 ε P נאמר כי p1 הוא לפני p2 ונסמן p1<p2  אם:

1)                p1 קצר מ-p2 , כלומר קצר באורך הסדרה, ב-p1 יש פחות זוגות מב-p2.

      2)                האורך של p1, p2 זהה, ן- p1 מופיע לפני p2 בסדר הלקסיקוגרפי על P.

 

טענת עזר: קיימת מ"ט דטרמיניסטית MP לכל סדרה pεP . אם נותנים ל- MP את p כקלט,

אזי  MP עוצרת כאשר הסדרה הבאה לפי סדר, בפלט.

כלומר: MP=(QP, ∑P,δP,sP,hP) ן- QA× (∑AU{R,L}) з ∑P (ז"א שחלק מהסימנים של MP

זה זוגות של מצב ופעולה).

מתקיים לכל pεP  ---- (hp,#p'#)|(sp,#p#) p<p'  ובדיוק הבא בתור אחרי p.

 

 

 27-01-04 / 09:48  עודכן ,  20-01-04 / 13:00  נוצר ע"י שמרית דויטש  בתאריך 
 מכונת טיורינג לא דטרמיניסטית - הקודםהבא - אלגוריתם השקילות 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 5