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

יהי $\Sigma$ אלפבית, תהיינה $f,g:\Sigma^*\to\Sigma^*$ פונקציות, ותהיינה $M_f,M_g$ מכונות טיורינג המחשבות את $f,g$, בהתאמה. תהא $h:\Sigma^*\to\Sigma^*$ פונקציית ההרכבה

$$h(x)=f(g(x)).$$

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