יהי אלפבית, תהיינה 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))$$

לכל $x\in\Sigma^*$.

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_h,M_A$ ניתן להגדיר מכונת טיורינג $M_B$ אשר מכריעה את השפה $B$. תארו היטב את הגדרת המכונה והראו שהיא אכן מכריעה את $B$. יש להגדיר מכונה יעילה ככל האפשר.
3. נניח כי לכל $x\in\Sigma^*$, $$time_{M_g}(x)\le O(|x|^3),$$ $$time_{M_f}(x)\le O(|x|^5),$$ $$time_{M_A}(x)\le O(|x|^{10}).$$ חשבו חסמים מלמעלה על זמן הריצה ועל סיבוכיות המקום של:
   1. המכונה $M_h$;
   2. המכונה $M_B$.
4. כיצד ישתנה החסם על זמן הריצה של $M_B$ בסעיף 3 אם ידוע בנוסף כי לכל אחת מן המכונות $M_g,M_f,M_A$ יש $10$ סרטים, בעוד שהמכונה $M_B$ צריכה להיות מכונה סטנדרטית? נסו להשיג חסם קטן ככל האפשר.
5. כיצד ישתנה החסם על זמן הריצה של $M_B$ בסעיף 4 אם ידוע בנוסף כי לכל $x\in\Sigma^*$, $$space_{M_g}(x)\le O(|x|),$$ $$space_{M_f}(x)\le O(|x|),$$ $$space_{M_A}(x)\le O(|x|)?$$ נסו להשיג חסם קטן ככל האפשר.