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

הוכחת המשפט

 

כהקדמה להוכחה נצטרך להגדיר את הסרט הבא: סרט המחולק למספר מסלולים, כלומר כל תו בסרט הוא למעשה טור של אוסף תוים.

דוגמא:

 

a f s
r e #
l e q

 

התו הראשון בסרט הוא השלישייה s,#,q .

התו השני בסרט הוא השלישייה f,e,e . וכן הלאה. 

כעת נעבור להוכחה:

המכונה M היא מקרה פרטי של המכונה N . מציבים K=1 וסיימנו.

לכן נוכיח את הכיוון השני:

 

 נבנה את המכונה M שתבצע סימולציה של פעולות N כל צעד.

 

הרעיון: נחלק את הסרט של M ל- 2K מסלולים. המסלול ה- 2I-1 יכיל את תוכן הסרט ה-I של N  והמסלול ה- 2I יסמן את מיקום הראשבסרט ה- I .

וכעת לאלגוריתם:

1) נזיז את תוכן הסרט משבצת אחת ימינה, ונוסיף $ בקצה השמאלי.

דוגמא: אם תוכן הסרט הוא baa  , אזי בשלב זה הסרט יראה כך:

 

# a a b # s

 

 כמובן, שאחרי המחרוזת יש אינסוף #-ים.

 2) נסרוק את הסרט מימין לשמאל (עד $) ונפריד ל- 2K מסלולים,כאשר במסלול הראשון נכתוב את תוכן הסרט הקיים, במסלול השני נכתוב X במשבצת הראשונה, במסלול 2I-1 (עבור I> 1 ) נכתוב #,

ובמסלול 2I, נכתוב X במשבצת השמאלית ביותר, ו- # בשאר המשבצות.

נחזיר את הראש קורא- כותב למשבצת מימין לחלק המופרד למסלולים.

בדוגמא שלנו זה יראה כך:

 

# # a a b # $
x
# # # # #
# # # # x

 

בסוף שלב זה הראש יצביע על ה-# הימני ביותר (העליון, שמתחתיו אין שום תו).

3) את ה- CPU של המכונה M נחלק למספר אוגרים:באוגר state נכתוב s , ובאוגרים tape i , נכתוב *. 

4) סריקה של הסרט מימין לשמאל ( עד $ ) תוך כדי מילוי tape i, ז"א מה שמעל X נשים באוגרים. 

5) תוך כדי התייעצות בטבלת מעברים של N ועל סמך תוכן האוגרים state ו- tape i , נכתוב תוכן האוגרים state  ו- action i , כאשר i רץ בין 1 ל- k .

  

 הטבלא N היא סופית, לכן היא יכולה לקבוע באופן חד- ערכי את הטבלא  

של M

 

6) מעבר לצד ימין של החלק המופרד למסלולים.

7) עבור i=1....k

א. סריקה מימין לשמאל עד ה-$ וביצוע הפעולה action i ,על סרט i.

כל זה צעד בודד של המכונה N

ב. אם state=h, אזי: להוריד $ מהקצה השמאלי, למחוק מסלולים נוספיםולהשאיר מסלול ראשון בלבד, להעביר את הראש למיקום ה X במסלולהשני, למחוק X ולעצור. 

ג. אם באחת מהפעולות של action i יש נסיון להזיז X ל-$, אזי המכונהM עוברת שמאלה,

 משמאל ל-$ ויש נפילה של המכונה. 

8) כתיבת * באוגרים tape i וחזרה לשלב 4.

 

 מקרה של לולאה אינסופית אין צורך לבצע דבר,היות ו-M מבצעת  

סימולציה ל-N

 

 

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