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

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

דורון זוהר

 

שאלה 1

בנה מכונת טיורינג המקבלת כקלט שני מספרים חיוביים a,b>0, הכתובים באונרית ונותנת כפלט את הערך 2a+b.

על המכונה לעבוד לפי מוסכמות הכתיבה שתוארו בחומר הלימוד.

 

פתרון

המכונה תעבוד עפ"י האלגוריתם הבא. ראשית היא תסמן $ במילת הפלט.

עתה, על כל 1 בנתון הקלט הראשון היא תרשום שתי אותיות 1 בפלט.

לאחר מכן, על כל אות 1 בנתון הקלט השני היא תוסיף אות 1 אחת בפלט.

לבסוף תסיים בכתיבת $ נוסף במילת הפלט.

א"ב הקלט הוא {1,#}. א"ב המכונה הוא {$,1,X,Y}. למכונה תשעה מצבים:

q0 – מצב התחלתי.

q1 – מצב בו המכונה מחפשת תא ריק ראשון לכתיבת $.

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

q3 – המכונה מצפה לראות את האות הבאה לסימון בנתון הקלט הראשון או סימן חוצץ. 

q4 – סומנה אות בנתון הקלט הראשון ויש להגיע למילת הפלט ולכתוב בה 11.

q5 – סומנה אות בנתון הקלט הראשון, נכתבה אות 1 במילת הפלט ויש לכתוב עוד אות 1.

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

q7 – המכונה מצפה לראות את האות הבאה לסימון (שנייה ויותר) בנתון הקלט השני. 

q8 – סומנה אות בנתון הקלט השני ויש להגיע למילת הפלט ולכתוב בה 1.

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

q10 – הסתיימה קריאת הנתון השני, יש לכתוב $ שני במילת הפלט.

q11 – מצב מקבל.

המעברים:

סריקה ימינה עד התא הריק הראשון –

(ימין ,1 (q0, 1, q1,

 

(ימין ,# (q1, #, q1,

כתיבת $ ראשון בפלט –

(שמאל ,$ (q1, Δ, q2,

סריקה שמאלה עד האות הבאה לסימון בנתון הראשון –

(שמאל ,1 (q2, 1, q2,

 

(שמאל ,$ (q2, $, q2,

 

(שמאל ,# (q2, #, q2,

זיהוי האות האחרונה שסומנה בנתון הראשון –

(ימין ,X (q2, X, q3,

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

סימון אות 1 תורנית בנתון הראשון –

(ימין ,X (q3, 1, q4,

סריקה ימינה עד התא הריק הראשון –  

(ימין ,1 (q4, 1, q4,

 

(ימין ,# (q4, #, q4,

 

(ימין ,$ (q4, $, q4,

כתיבת 1 ראשון (מתוך 11) במילת הפלט –

(ימין ,1 (q4, Δ, q5,

כתיבת 1 שני (מתוך 11) במילת הפלט –

(שמאל ,1 (q5, Δ, q2,

הסתיימה קריאת הנתון הראשון –

(ימין ,# (q3, #, q6,

סומנה אות ראשונה בנתון השני –

(ימין ,Y (q6, 1, q8,

סריקה ימינה עד התא הריק הראשון –

(ימין ,1 (q8, 1, q8,

 

(ימין ,$ (q8, $, q8,

סימון 1 במילת הפלט –

(שמאל ,1 (q8, Δ, q9,

סריקה שמאלה עד האות הבאה לסימון בנתון השני –

(שמאל ,1 (q9, 1, q9,

 

(שמאל ,$ (q9, $, q9,

זיהוי האות האחרונה שסומנה בנתון השני –

(ימין ,Y (q9, Y, q7,

סומנה אות שנייה ויותר בנתון השני –

(ימין ,Y (q7, 1, q8,

הסתיים הנתון השני.

סריקה ימינה עד כתיבת $ שני במילת הפלט –

(ימין ,$ (q7, $, q10,

 

(ימין ,1 (q10, 1, q10,

סיום כתיבת מילת הפלט –

(ימין ,$ (q10, Δ, q11,

 

נשים לב שבמקרה זה הדרישה a,b>0 (ולא a,b³0) חייבה הוספת מצבים. אחרת ניתן היה לאחד את q0 ו-q1  ואת q6  ו-q7.

 

חזרה

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

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