» נושאי לימוד
» נושאי לימוד
יום שלישי 19 במרץ 2024
פתרון שאלה 9
דף ראשי  תגבור  פתרונות  פתרון שאלה 9 גרסה להדפסה

פתרון שאלה 9

 

נוכיח כי התוכנית הבאה שקולה למכונת הטיורנג שתוצג בהמשך:

 

הרעיון:

 

נגדיר מכונת טיורינג M שתכיל סרט קלט אחד (שלא ייעשה בו שימוש), ו-3 סרטי עבודה כנגד שלושת המשתנים שבתוכנית: X,Y,Z בהתאמה.

המכונה תהיה מורכבת ממספר מצבים (לפחות כמספר שורות הקוד).

 

טבלת המעברים של M:

 

מצב אות מצב חדש פעולה הערות פעולה
L1 #,#,#,# write.1.1 #,#,R,# נכתוב 3 אחדים בסרט של X 1) X=3
write.1.1 #,#,#,# write.1.1 #,#,1,# כתיבת 1 ראשון
write.1.1 #,#,1,# write.1.2 #,#,R,# תזוזה
write.1.2 #,#,#,# write.1.2 #,#,1,# כתיבת 1 שני
write.1.2 #,#,1,# write.1.3 #,#,R,# תזוזה
write.1.3 #,#,#,# write.1.3 #,#,1,# כתיבת 1 שלישי
write.1.3 #,#,1,# L2 #,R,R,# תזוזה של ראש X ימינה, והכנת סרט Y
L2 #,#,#,# L2 #,1,#,# כתיבת 1 בסרט Y
L2 #,1,#,# L3 L,R,R,# תזוזה לקצה Y חזרה לשטח X לקראת הפקודה הבאה, והכנת Z
L3 #,#,1,# L3 1,#,1,# העתקת 1 מ X ל Y 3) Z=X
L3 1,#,1,# L3 R,#,L,# תזוזות
L3 #,#,#,# L4 L,#,#,# חזרה לשטח Z לפקודה הבאה
L4 #,#,#,# L8 #,#,#,# אם סרט Z ריק, כלומר Z=0 4) IF Z=0 THEN GOTO 8
L4 1,#,#,# L5 R,#,#,# סרט Z לא ריק לכן ממשיכים הלאה
L5 #,#,#,# L5 #,1,#,# הוספת 1 לסוף סרט Y 5) Y=Y+1
L5 #,1,#,# L6 R,L,#,#
L6 1,#,#,# L7 #,#,#,# הורדת 1 מסוף סרט Z 6) Z=Z-1
L7 #,#,#,# L4 L,#,#,# 7) GOTO 4
L8 #,#,#,# H #,#,#,# 8) End

 

 
 09-02-04 / 11:05  עודכן ,  29-01-04 / 22:15  נוצר ע"י שמרית דויטש  בתאריך 
 פתרון שאלה 8 - הקודםהבא - פתרון שאלה 10 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 3