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

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

דגנית מורן

 

שאלה 1

בנה מכונת טיורינג המקבלת כקלט מספר שלם x>0 הכתוב באונרית, ומחשבת את הפונקציה:

 

פתרון

המכונה תעבוד על פי האלגוריתם הבא:

במקום האות הראשונה במילת הקלט תכתוב את סימן ה-$ הפותח את מילת הפלט.

כעת תמחק את כל שאר אותיות מילת הקלט, תוך מעקב אחר זוגיות מספר האותיות שקראה.

אם כאשר הסתיימה המילה נקרא מספר אי-זוגי של אותיות תחזור אחורה ותכתוב סימן $ נוסף מימין לסימן ה- $ הראשון.

אם נקרא מספר זוגי של אותיות תחזור אחורה ומימין לסימן ה-$ הראשון תכתוב אות 1 ואחריה סימן $ נוסף.

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

למכונה שמונה מצבים:

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

q1 – זוכר כי נכתב סימן $ ראשון וכי נקרא מספר אי-זוגי של אותיות 1.

q2 – זוכר כי נכתב סימן $ ראשון וכי נקרא מספר זוגי של אותיות 1.

q3 – זוכר כי הסתיימה מילת הקלט והיא מייצגת מספר זוגי.  

q4 – זוכר כי הסתיימה מילת הקלט והיא מייצגת מספר אי-זוגי. 

q5 – זוכר כי הסתיימה מילת הקלט, היא מייצגת מספר זוגי ובתא הנוכחי יש לכתוב 1.

q6 – זוכר כי יש עוד לכתוב סימן $ לסגירת מילת הפלט.  

q7 – מצב מקבל.

 

נתאר את המכונה בצורה גרפית.

 

חזרה

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

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