מכונת טיורינג עם K סרטים
מאפיינים:
ü בקר מרכזי בודד.
ü K סרטים כך שלכל סרט יש ראש קורא-כותב עצמאי, בלי תלות בראשים האחרים.
ü בכל צעד הבקר המרכזי עובר למצב חדש, ומתבצעת פעולה נפרדת בכל אחד מהסרטים.
הגדרה: במכונה עם k סרטים, פונקצית המעברים d הינה פונקציה:
שימוש במכונה עם k סרטים:
הקלט/ פלט בסרט הראשון כמו במכונה רגילה.
בהתחלה, הסרטים הנוספים ריקים לגמרי והראש בקצה השמאלי.
בסוף, סרטי העזר במצב כלשהו.
דוגמא: נסתכל על מכונה עם שני סרטים, כלומר k = 2
בהנתן קלט: abbab נרצה כפלט את המילה ההפוכה babba
משפט: תהי S,h),(Q,S,d =N מכונת טיורינג עם k סרטים, אזי קיימת מכונת טיורינג
S',h'),'(Q',S',d =M כך ש: " M שקולה ל – N " במובן הבא:
לכל (S - { # } ) w Îמתקיים:
אז במכונה M
2) בהנתן קונפיגורציה ( s, #w#, #,…, # ) המכונה N לא עוצרת, או בהנתן הקונפיגורציה ( s ‘, #w# ) המכונה M לא עוצרת.
3) כמו 2) לגבי נפילה: אם N נופלת אז גם M נופלת.
|
|
מכונה שאיננה עוצרת, זו לא בהכרח מכונה שנכנסה ללולאה אינסופית, וגם לא בהכרח ידוע לנו שהיא לעולם לא תעצור.
גולשים מקוונים: 2