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

פתרון שאלה 3

 

נוכיח כי הטענה נכונה.

 

תהי מכונת טיורינג M', M'=(S,K,s,H,d'). המכונה גם כותבת וגם זזה בשלב אחד. 

 

פונקציה ניתנת לחישוב על-ידי M => הפונקציה ניתנת לחישוב על-ידי M':

תהי f פונקציה הניתנת לחישוב על-ידי מכונת טיורינג M=(S,K,s,H,d).

נבנה מכונת טיורינג M'=(S',K',s',H',d') כך ש- S'=S, s'=s, H'=H, K'=K U K'' (K'' תוגדר בהמשך).

 

נגדיר את d':

 לכל מעבר ב-d מהצורה d(p1,c1) = (p2, R/L) נתאים מעבר ב-d' מהצורה:

 d'(p1,c1) = (p2,c1,R/L).

 לכל מעבר ב-d מהצורה d(p1,c1) = (p2,c2) נתאים ב-d' את המעברים:

1.         d'(p1,c1) = (p12,c2,R).

2.        d'(p12,*) = (p2, *,L).

כלומר: כותבים את האות, עוברים למצב ביניים, וחוזרים חזרה בתזוזה הפוכה.

K'' = כל מצבי הביניים.

הראינו כי כל פעולות d מתורגמות לאותו ביצוע כמו פעולות d' המתאימות, ולכן גם M' מחשבת את f.

 

פונקציה ניתנת לחישוב על-ידי M' => הפונקציה ניתנת לחישוב על-ידי M:

 

תהי f פונקציה הניתנת לחישוב על-ידי M': M'=(S',K',s',H',d').

נבנה מכונת טיורינג M=(S,K,s,H,d) כך ש-  S=S', s=s', H=H', K=K' U K''.

נגדיר את d:

לכל מעבר ב-d' מהצורה d'(p1,c1) = (p2,c2,R/L) נתאים מעברים ב-d (לא ניתן גם לכתוב וגם לזוז ב-d):

1.        d(p1,c1) = (p12,c2)

2.        d(p12,c2) = (p2,R/L)

הערות:

1.        כל מצבי pij  (מצבי הביניים) הנ"ל יהוו את K''.

 2.    המכונה החדשה אינה חזקה יותר מהמכונה המקורית. כל דבר במכונה החדשה ניתן לבצע

גם במקורית.

 09-02-04 / 10:49  עודכן ,  29-01-04 / 20:51  נוצר ע"י שמרית דויטש  בתאריך 
 פתרון שאלה 2- המשך - הקודםהבא - פתרון שאלה 4 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 5