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

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

תהיינה $f,g:\mathbb N\to\mathbb N$. נניח כי:

1. $f$ ישימה בזמן;
2. $f$ סופר־לינארית: $f(n)\ge n$ לכל $n\in\mathbb N$;
3. $g=o(f)$.

אז

$$DTime(g)\subsetneq DTime(f^2).$$

השתמשו בשפה

$$T_f=\left\{\langle M\rangle\#^n\ \middle|\ n\text{ טבעי},\ M\text{ דוחה את }\langle M\rangle\#^n,\ time_M(\langle M\rangle\#^n)\le\frac{f(|\langle M\rangle\#^n|)}{|\langle M\rangle|}\right\}.$$

הסימון $\langle M\rangle\#^n$ הוא קידוד של מכונת טיורינג $M$ ולאחריו $n$ מופעים של $\#$, שאינו תו באלפבית של $M$.

• הוכיחו כי $T_f\in DTime(f^2)$. חזרו על ההוכחה מן השיעור ש-$S_f\in DSpace(f)$. כאן דרוש מונה זמן בלבד, והריבוע נובע מן המעבר ממכונה רב־סרטית למכונה חד־סרטית ומהקשר בין מדדי הזמן והמקום של הסימולציה.
• הוכיחו כי $T_f\notin DTime(g)$. השימוש בהגדרת הגבול דומה, אך במקום "לנפח" את המכונה מנפחים את התוספת לקידודה. הסבירו מדוע ניפוח המכונה אינו עובד כאן.

הסיקו את משפט היררכיית הזמן.