מאגר שאלות ותשובות להוראת מודלים חישוביים:

בניית מכונות טיורינג

ריקה רם

 

שאלה 1

בנה מכונת טיורינג המקבלת מספר טבעי n ביצוג אונארי ומחשבת את השארית השלמה של חלוקת המספר ב-3.

כלומר f(n)=n mod 3 כאשר n³0.

 

פתרון

בכל שלב המכונה תזהה שלשת אותיות 1 ואם מצאה שלשה – תמחק אותה.

בשלב הסיום תקיף המכונה את מה שנותר על הסרט ב- $.

א"ב הקלט הוא {1} וא"ב המכונה הוא {$}.

המצבים:

q0 – מצב התחלתי ומצב תחילת שלב מציאת שלשה.

q1 – זוכר כי נקרא 1 ראשון בשלשה.

q2 – זוכר כי נקרא 1 שני בשלשה.

q3 – זוכר כי נקרא ונמחק 1 שלישי בשלשה. מפנה שמאלה להמשך מחיקת השלשה.

q4 – זוכר כי נמחק 1 שני בשלשה.

q5 – זוכר כי נמחק 1 ראשון בשלשה.

q6 – זוכר כי דולגה אות מחוקה שניה.

q7 – זוכר כי סומנה אות $ ימנית, פונה שמאלה לחיפוש המקום לסימון אות $ שמאלית. 

q8 – במקרה שיש צורך בהזזת הפלט לצורך סימון אות $ שמאלית (כאשר n<3), המצב זוכר כי סומנה אות $ שמאלית ויש להשלים עוד 1 שנמחק.

q9 – זוכר כי יש להשלים עוד אות $ ימנית שנמחקה.

q10 – מצב סיום תהליך. 

q10 הוא המצב המקבל.

אלו המעברים:

קריאת 1 ראשון בשלשה –

קריאת 1 שני בשלשה –

קריאת ומחיקת 1 שלישי בשלשה –

מחיקת 1 שני בשלשה –

מחיקת 1 ראשון בשלשה –

דילוג על 1 מחוק שני בשלשה –

דילוג על 1 מחוק שלישי בשלשה –

נשארה שארית 1. סימון קצה ימני של הפלט –

נשארה שארית 2. סימון קצה ימני של הפלט –

נשארה שארית 0. סימון קצה ימני של הפלט –

דילוג שמאלה בדרך לחיפוש מקום לסימון קצה שמאלי של הפלט –

סימון קצה שמאלי ומעבר למצב סיום –

סימון קצה שמאלי ויש צורך בהזזת הפלט –

המשך הזזת הפלט –

הושלם 1 שנמחק במסגרת ההזזה ויש צורך בסימון קצה קלט ימני חדש –

סימון קצה ימני ומעבר למצב סיום –

 

חזרה

למאגר החומרים

לאתר מודלים חישוביים