מכונת טיורינג המקבלת בתחילת הסרט שני מספרים אונריים שביניהם הסימן #. מצב התחלתי q0, מצב מקבל q7. תווי הסרט: 1, #, Δ (תא ריק), ＄, ⊢ (תחילת הסרט). כל מעבר רשום כ«נקרא/נכתב, כיוון».
מכונת טיורינג המקבלת בתחילת הסרט שני מספרים אונריים שביניהם הסימן #. מצב התחלתי q0, מצב מקבל q7. תווי הסרט: 1, #, Δ (תא ריק), ＄, ⊢ (תחילת הסרט). כל מעבר רשום כ«נקרא/נכתב, כיוון».
טבלת המעברים של המכונה (נקרא / נכתב, כיוון → מצב הבא):
q0: 1 / Δ, ימין → q1 # / ＄, ימין → q8
q1: 1 / 1, ימין → q1 # / #, ימין → q2
q2: 1 / 1, ימין → q2 Δ / Δ, שמאל → q3
q3: 1 / Δ, שמאל → q4 # / ＄, שמאל → q5
q4: 1 / 1, שמאל → q4 # / #, שמאל → q4 Δ / Δ, ימין → q0
q5: 1 / 1, שמאל → q5 Δ / 1, שמאל → q6
q6: Δ / ＄, ימין → q7 (מקבל)
q8: 1 / 1, ימין → q8 Δ / ＄, ימין → q7 (מקבל)
הסרט של סעיף א:
הסרט של סעיף ב:
סעיף א
עקבו אחר המכונה עבור הסרט שלהלן: ⊢ | 1 | # | 1 | 1 | 1 | Δ | Δ | … כתבו מה יתקבל על הסרט בסיום הפעולה.
סעיף ב
כתבו מה יתקבל על הסרט שלהלן בסיום הפעולה: ⊢ | 1 | 1 | # | 1 | Δ | Δ | … הערה: בסעיף זה אין צורך להראות מעקב.
סעיף ג
מה המכונה מבצעת עבור שני מספרים אונריים הגדולים מאפס?
סעיף ד
לפניכם שלושה מקרים, 1–3. בעבור כל מקרה ציינו אם המכונה פועלת נכון או לא נכון. אם המכונה פועלת נכון, הציגו באמצעות דוגמה את סרט הקלט ואת סרט הפלט. אם המכונה פועלת לא נכון, הסבירו מדוע.
- המספר הראשון (משמאל) שווה לאפס והמספר השני גדול מאפס.
- המספר השני שווה לאפס והמספר הראשון גדול מאפס.
- שני המספרים שווים לאפס.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.