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

מכונת טיורינג עם K סרטים

 

מאפיינים:  

       ü           בקר מרכזי בודד.

       ü           K  סרטים כך שלכל  סרט יש ראש קורא-כותב עצמאי, בלי תלות בראשים האחרים.

       ü           בכל צעד הבקר המרכזי עובר למצב חדש, ומתבצעת פעולה נפרדת בכל אחד מהסרטים. 

 הגדרה: במכונה עם k  סרטים, פונקצית המעברים d הינה פונקציה:

{ L /  R } ]  k                        [ Q x S È   ] x Sk  d: [ ( Q – { h } )

 

שימוש במכונה עם k  סרטים:

הקלט/ פלט בסרט הראשון כמו במכונה רגילה.

בהתחלה, הסרטים הנוספים ריקים לגמרי והראש בקצה השמאלי.

בסוף, סרטי העזר במצב כלשהו.

 

דוגמא: נסתכל על מכונה עם שני סרטים, כלומר k = 2

                 בהנתן קלט: abbab  נרצה כפלט את המילה ההפוכה babba

 

 

 

משפט: תהי S,h),(Q,S,d =N  מכונת טיורינג עם k  סרטים, אזי קיימת מכונת טיורינג

 S',h'),'(Q',S',d =M  כך ש: " M  שקולה ל – N  במובן הבא:

לכל  (S - { # } )     w Îמתקיים:

         1)           אם:… u k  a k vk )   ( h, u1 a1 v1,       N *      ( s,  #w#, #,…, # )

        אז במכונה

 h ‘, u a v  )                                       (      M *       ( s ‘,  # w # )

                                                                     

2)   בהנתן קונפיגורציה  ( s,  #w#, #,…, # )  המכונה N לא עוצרת, או בהנתן הקונפיגורציה  ( s ‘,  #w# ) המכונה M   לא עוצרת.

 

3)    כמו 2)  לגבי  נפילה: אם  N  נופלת אז גם M   נופלת.

 

 

 מכונה שאיננה עוצרת, זו לא בהכרח מכונה שנכנסה ללולאה אינסופית, וגם לא בהכרח ידוע לנו שהיא לעולם לא תעצור.

 

 22-03-04 / 10:58  עודכן ,  31-12-03 / 21:43  נוצר ע"י שמרית דויטש  בתאריך 
 הכרעת שפות - הקודםהבא - מכונה עם K סרטים- הוכחת המשפט 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 3