הרכבת תת־שגרות של מכונת טיורינג

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

שאלה

המכונה $M_f$ מחשבת את $f(x)$ בזמן $t_f(n)$ ובמקום עבודה $s_f(n)$. המכונה $M_g$ מכריעה אם $f(x)\in B$ בזמן $t_g(m)$ ובמקום $s_g(m)$ לקלט באורך $m$. בנו מכריע רב־סרטי עבור $A=\{x:f(x)\in B\}$ וגזרו חסמי זמן ומקום מדויקים, לרבות שימוש חוזר בסרט פלט הביניים.

דרישות קדם

נדרשת שליטה בהגדרות היחידה ובניתוח אורכי קידוד. יש להבחין בין טענה מותנית, רדוקציה ואלגוריתם.

רמז 1

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

רמז 2

הגדירו בנפרד $\ell(n)$ כחסם על $|f(x)|$.

רמז 3

בניתוח מקום הפרידו קלט לקריאה בלבד, מחרוזת ביניים וסרטי עבודה הניתנים למחזור.

פתרון מלא

נשתמש בסרטים נפרדים לקלט המקורי, לערך הביניים ולזיכרון עבודה. תחילה מדמים את $M_f$ ומשאירים $y=f(x)$ על סרט הביניים. לאחר מכן מאפסים או ממחזרים את סרטי העבודה ומדמים את $M_g$ על $y$. לכן

שתי המכונות עוצרות ולכן גם המכונה המורכבת עוצרת.

נסמן $\ell(n)=\max_{|x|=n}|f(x)|$. באלפבית קבוע כתיבת סימן דורשת צעד, ולכן $\ell(n)=O(t_f(n))$. החסם הישיר במודל רב־סרטי הוא

האיבר האחרון מכסה העתקה או מיקום מחדש, ובדרך כלל נבלע באחרים. אם כל הפונקציות פולינומיות, גם ההרכבה פולינומית.

במקום יש לשמור בפועל את $y$. בשלב הראשון דרושים $\ell(n)+s_f(n)$ תאים; בשלב השני $\ell(n)+s_g(\ell(n))$. זיכרון נמדד לפי המקסימום בו־זמני ולא לפי סכום היסטורי, ולכן

אם הגדרת המקום של $M_f$ כבר כוללת את סרט הפלט, אז $\ell(n)\le s_f(n)$ ואפשר לפשט למקסימום. אם סרט הפלט אינו מחויב, אסור להשמיט את $\ell(n)$ בלי טיעון זרימה מפורש.

בסרט יחיד עשויה להיות תקורת זמן פולינומית לסימולציה, אך מסקנת הסגירות הפולינומית נשמרת. הניתוח התקין מציין את מודל המכונה, את קונבנציית סרט הפלט ואת חסם אורך הביניים, ולא מסתפק באמירה ״פולינום אחרי פולינום״.

נקודות בדיקה

בדקו שהוכחתם את שני הכיוונים, שכל ענף או מכונה עוצרים, ושגודל הפלט וזמן הבנייה פולינומיים באורך הקלט.

טעויות נפוצות

• הצבת $t_g(n)$ במקום $t_g(|f(x)|)$.
• חיבור מקום השלבים במקום לקיחת מקסימום.
• השמטת מחרוזת הביניים כשהפלט אינו מחויב.

מקורות ואימות

• Merged summary, pp. 14-20
• 2026 transcript 2
• Sipser 3e, secs. 3.2 and 7.1
• מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

התרגיל הוא סינתזה מקורית. רמת הביטחון משקפת אימות של הטענה המתמטית מול מקורות ספרי הלימוד המפורטים לעיל; מקורות הקורס משמשים רק כאשר זוהה כיסוי ישיר.