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

מכונת טיורינג למנייה

 

דוגמא: מ"ט למנייה של {a}*

1)       כתיבת $ בסרט 1.

2)       תזוזה ימינה בסרט 2 וכתיבת a.

3)       שמאלה בסרט 2 עד ה-#, ומשבצת אחת ימינה בסרט 1.

4)       העתקת a-ים מסרט 2 לסרט 1 עד ל-# בסרט 2.

5)       כתיבת $ בסרט 1 וכתיבת a בסרט 2.

6)       חזרה לשלב 3.

 

משפט: תהי L שפה. קיימת מ"ט M שמקבלת את L  אמ"ם קיימת מ"ט C למנייה של שפה

שמונה את L.

הוכחה:

מנייה ← קבלה: תהי C מ"ט שמונה את L . נבנה מ"ט M שמקבלת את L .

M תפעיל את C. אחרי כל כתיבה של מילה u בפלט של C, נבדוק האם w=u.אם כן,

המכונה תעצור, אחרת ניתן ל-C להמשיך לפעול. אם C עוצרת,M נכנסת ללולאה אינסופית.

 

קבלה ← מנייה: אם M לא עוצרת על u, אז לכל i, M לא עוצרת על u ב-i צעדים,

 וממילא C לא תכתוב u בפלט.

 

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