תהיינה M f,M g מכונות טיורינג אשר מחשבות את הפונקציות

תהיינה $M_f,M_g$ מכונות טיורינג אשר מחשבות את הפונקציות

$$f,g:\Sigma^*\to\Sigma^*$$

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

$$h:\Sigma^*\to\Sigma^*, \qquad h(x)=f(g(x))$$

פונקציית ההרכבה.

1. הסבירו כיצד, בהינתן המכונות $M_f,M_g$, ניתן להגדיר מכונת טיורינג $M_h$ אשר מחשבת את $h$. תארו היטב את הגדרת המכונה והראו שהיא אכן מחשבת את $h$.
2. תהא $M_A$ מכונת טיורינג שמכריעה שפה $A\subseteq\Sigma^*$. נגדיר $$B=\{x\in\Sigma^*\mid h(x)\in A\}.$$ הסבירו כיצד, בהינתן $M_A,M_h$, ניתן להגדיר מכונת טיורינג $M_B$ אשר מכריעה את $B$. תארו היטב את הגדרת המכונה והראו שהיא אכן מכריעה את $B$.
3. נניח שזמן הריצה של $M_g$ על קלט באורך $n$ הוא $O(n^3)$, זמן הריצה של $M_f$ על קלט באורך $n$ הוא $O(n^6)$, וזמן הריצה של $M_A$ על קלט באורך $n$ הוא $O(n^9)$.
   1. מה ניתן לומר על אורך הפלט של $M_g$ בריצתה על קלט באורך $n$?
   2. מה ניתן לומר על אורך הפלט של $M_f$ בריצתה על קלט באורך $O(n^3)$?
   3. חשבו חסמים עליונים על זמן הריצה ועל סיבוכיות המקום של המכונות $M_h,M_B$ בריצתן על קלט באורך $n$.