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

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

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

נגדיר

$$h_1(x)=f(x)\oplus g(x), \qquad h_2(x)=f(g(x)),$$

כאשר $\oplus$ מסמן שרשור מחרוזות.

1. תארו מכונות טיורינג סטנדרטיות בעלות סרט יחיד $M_{h_1},M_{h_2}$ המחשבות את $h_1,h_2$, בהתאמה.
2. נניח שזמן הריצה של $M_g$ על קלט באורך $n$ הוא $O(n^3)$, וזמן הריצה של $M_f$ על קלט באורך $n$ הוא $O(n^7)$. חסמו את אורך הפלט ואת סיבוכיות הזמן והזיכרון של $M_{h_1}$ ושל $M_{h_2}$. נסו לתת חסמים הדוקים ככל האפשר.