שאלה 9 במסלול מודלים חישוביים. נתונה הפעולה compare (java) / Compare (C#) המשווה שני מספרים שלמים חיוביים n1,n2 ומחזירה 1 אם n1>=n2 אחרת 2. יש לבנות מכונת טיורינג הממממשת פעולה זו: n1,n2 כתובים על הסרט באונרית (ספרת 1 בלבד), מופרדים בסימן # יחיד, ואת התוצאה יש לרשום באונרית בין שני סימני $ במיקום כלשהו על הסרט.
שאלה 9 במסלול מודלים חישוביים. נתונה הפעולה compare (java) / Compare (C#) המשווה שני מספרים שלמים חיוביים n1,n2 ומחזירה 1 אם n1>=n2 אחרת 2. יש לבנות מכונת טיורינג הממממשת פעולה זו: n1,n2 כתובים על הסרט באונרית (ספרת 1 בלבד), מופרדים בסימן # יחיד, ואת התוצאה יש לרשום באונרית בין שני סימני $ במיקום כלשהו על הסרט.
public static int Compare(int n1, int n2)
{
if (n1 >= n2)
return 1;
return 2;
}
לפני הרצת המכונה
⊢ 1 1 # 1 1 1 Δ Δ Δ
אחרי הרצת המכונה
⊢ . . $ 1 1 $ .
בנו מכונת טיורינג הממממשת את הפעולה. המכונה מקבלת 2 מספרים שלמים גדולים מ-0 הכתובים במספרים שלמים בסיס-1 (unary, ספרות 1 בלבד) ומיוצגים בשפה בשפה אונרית (ע"י הספרה 1 בלבד). בין שני המספרים מופיע הסימן # (בין שני המספרים מופיע # בלבד). את הערך המוחזר מהפעולה יש לרשום בין 2 סימני ＄ במיקום כלשהו על הסרט. דוגמה, לפני הרצת המכונה: ⊢ 1 1 # 1 1 1 Δ Δ Δ אחרי הרצת המכונה: ⊢ . . ＄ 1 1 ＄ . הסבר: המספר הראשון n1=2 והמספר השני n2=3 ולכן המספר שהמכונה מחזירה הוא 2 (compare(2,3)=2, לכן ניתן לרשום את הערך המוחזר '11' -- שני אחדות המייצגות 2 באונרית -- באונרית).
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.