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

אלגוריתם השקילות

 

למכונה B יש שלושה סרטים: סרט קלט, סרט עבודה, סרט בחירות- choises. B תבצע סימולציה של המכונה A . state ישמור את המצב של המכונה שאנחנו מבצעים לה סימולציה. סרט העבודה יהיה כאילו הסרט של המכונה שאנו עושים לה סימולציה.

פעולות  המכונה B:

1)       כותבת $ בסרט העבודה, וזזה ימינה.

2)       זזה ימינה משבצת אחת בסרט הבחירות.

3)        מעתיקה קלט מסרט הקלט לסרט העבודה, אחרי ה-$.

4)        כותבת SA  באוגר state.

5)        מפעילה את המכונה MP על סרט הבחירות.

 

עכשיו אנחנו מוכנים לבצע את הסימולציה:

6)        זזה שמאלה משבצת אחת בסרט הבחירות.

7)        כותבת באוגר tape את הסימן שמתחת לראש שבסרט העבודה.

8)        נסמן ב- pair את התוכן של המשבצת שמתחת לראש הקורא בסרט הבחירות. אם pair=# עבור לשלב 9, אחרת בדוק האם ישנו המעבר בטבלת המעברים במ"ט הלא דטרמיניסטית. אם כן: עדכן את האוגר state  בהתאם, ובצע את הפעולה בסרט העבודה וחזור לשלב 6. אחרת המשך לשלב 9.

9)        מחק את תוכן סרט העבודה עד ל-$, עבור לקצה הימני של סרט הבחירות וחזור לשלב 3.

אם בשלב כלשהו התוכן של האוגר state הוא hA, אזי המכונה B עוצרת לחלוטין.

מתקיים:

אם קיים חישוב של A שעוצר על w , אזי קיימת סדרת זוגות p בסרט הבחירות, שתביא את הסימולציה למצב hA והמכונה B תעצור.

ומצד שני, אם A לא מקבלת את w, אזי לכל סדרת מעברים p, הסימולציה לא תגיע למצב hA , וממילא B לא תעצור.

 

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