1ממה ניתן לחשב למה ניתן לחשב ביעילות: המודל, המשאבים והמחלקות הבסיסיות

בקצרה

• הקורס הזה הוא המשך ישיר של חישוביות. שם שאלנו מה ניתן לחשב; כאן נשאל מה ניתן לחשב ביעילות — כלומר אנחנו עושים zoom-in לתוך המחלקה $R$ של הבעיות הכריעות ומחלקים גם אותה.
• "יעילות" איננה מושג אבסולוטי כמו "ניתן לחשב". צריך לומר יעיל במה — זמן, מקום, רוחב פס, ביטים אקראיים, דיוק — ולכן כל הגדרה בקורס תיאמר תמיד ביחס למשאב מסוים ולאורך הקלט.
• סרגל המדידה הוא מכונת טיורינג. המשאבים הבסיסיים הם $time_M(x)$ (מספר הפעלות פונקציית המעברים) ו-$space_M(x)$ (מספר התאים השונים שהמכונה כותבת בהם).
• מעברים בין מודלים עולים כסף, ואנחנו סופרים אותו: סימולציה של מכונה $k$-סרטית על ידי מכונה חד-סרטית עולה $O(time\cdot space)$ בזמן ואפס בסדר גודל במקום; המכונה האוניברסלית עולה פקטור של $|\langle M\rangle|$ בזמן ופקטור $\lg|\Gamma_M|$ במקום.
• הקשר בין זמן למקום אינו סימטרי: תמיד $space_M(x)\le time_M(x)$, אבל בכיוון ההפוך אין חסם כלל — אלא אם יודעים שהמכונה עוצרת, ואז $time_M(x)\le 2^{c_M\cdot space_M(x)}$ בעזרת ספירת קונפיגורציות.
• מכאן נגזרות שתי המחלקות הבסיסיות $DTime(f)$ ו-$DSpace(f)$ ושתי ההכלות $DTime(f)\subseteq DSpace(f)$ ו-$DSpace(f)\subseteq DTime\left(2^{O(f)}\right)$. אלה הלבנים שמהן ייבנה כל הקורס.

רקע ותלויות

זהו השיעור הראשון בסדרה, ולכן אין כאן הפניות לשיעורים קודמים בקורס. התלות היא כולה בקורס חישוביות שקדם לו. מה שצריך לזכור משם — ומה שנשתמש בו כאן ממש, ולכן נכתב במלואו:

1. מכונת טיורינג ופונקציית המעברים. מכונה היא אוסף סופי של מצבים, א"ב קלט/פלט, א"ב עבודה ופונקציית מעברים $\delta$ שרואה את המצב הנוכחי ואת התו שהראש הקורא־כותב עומד עליו, ומחליטה למה מצב לעבור, איזה תו לכתוב, ולאן להזיז את הראש. המצב הוא, כדברי המרצה, "כמו שורת קוד". הסרט אינו חסום מאף כיוון.

2. הווריאנט הרב-סרטי ומשפט השקילות. לכל $k$ קבוע מראש (לפני הקלט!) מוגדרת מכונה $k$-סרטית. משפט השקילות מחישוביות: לכל מכונה רב-סרטית $M$ קיימת מכונה חד-סרטית $\hat{M}$ מעל אותו א"ב קלט/פלט, כך שלכל $x\in\Sigma_M^*$ מתקיים $\hat{M}(x)=M(x)$. בחישוביות זה הספיק; בסיבוכיות נוסיף לזה מימד — כמה זה עולה.

3. המכונה האוניברסלית. קיימת מכונה $M_U$ שמקבלת קידוד של מכונה וקידוד של קלט ומריצה אותם. בחישוביות עניין אותנו רק שהיא קיימת; כאן נשאל כמה זמן ומקום היא צורכת.

4. המחלקות מחישוביות. $\mathrm{RE}$ — השפות שניתן לזהות; $coRE$ — המשלימות שלהן; $R$ — השפות שניתן להכריע. בחישוביות $R$ הייתה "הבעיות הקלות", מפני שלא שאלנו כלל כמה משאבים ההכרעה דורשת. כל הקורס הזה מתרחש בתוך $R$.

5. קידודים. כל דטה-טייפ (מספרים, קבוצות, גרפים) ניתן לייצוג כמחרוזת מעל א"ב קבוע, ולהיפך. לכן, כפי שנאמר בהקלטה [00:01:59], הדטה-טייפ פחות מעניין אותנו — מה שמעניין הוא הפונקציות ומודל החישוב.

6. סדר הכמתים. בסיבוכיות זה קריטי פי עשרה מאשר בחישוביות. כשכותבים "לכל $M$ קיים $c$ כך שלכל $x$", הקבוע $c$ מותר שיהיה תלוי ב-$M$ ואסור שיהיה תלוי ב-$x$ — פשוט מפני ש-$x$ מופיע אחריו.

הגדרות

הגדרה 1: מכונת טיורינג (חד-סרטית)

מכונת טיורינג היא

כאשר $Q$ קבוצת מצבים סופית, $q_{start}\in Q$ המצב ההתחלתי, $F\subseteq Q$ קבוצת המצבים הסופיים, $\Sigma$ א"ב הקלט והפלט, $\Gamma\supseteq\Sigma$ א"ב העבודה, ופונקציית המעברים

אינטואיציה. לפי הסיכום, $\delta$ "רואה" שני דברים בלבד — המצב הנוכחי והתו שמתחתיו הראש — ומחזירה שלושה: לאן לעבור, מה לכתוב, ולאן לזוז. אין למכונה זיכרון נוסף מעבר לזה: כל מה שהיא רוצה לזכור עליה לכתוב על הסרט או לקודד במצב.

על $F$. במכונת חישוב מסתפקים במצב סופי אחד, $q_H$; במכונת הכרעה בשניים בלבד, $q_{acc}$ ו-$q_{rej}$, והפלט נקבע לפי המצב שבו נעצרה הריצה. לכן בהרבה מקומות (וגם בסיכום) פשוט מוותרים על $F$ כרכיב נפרד בהגדרה. קונבנציה של הקורס [00:46:21]: אם לא נאמר אחרת במפורש, "מכונת טיורינג" פירושו מכונה סטנדרטית — חד-סרטית, וכל המדדים נמדדים ביחס אליה.

הגדרה 2: מכונת טיורינג $k$-סרטית

לכל $k\in\mathbb{N}$ הנקבע מראש, לפני הקלט, מכונה $k$-סרטית מוגדרת בדיוק כמו הגדרה 1 פרט לפונקציית המעברים:

אינטואיציה. בכל צעד המכונה קוראת תו אחד מכל אחד מ-$k$ הסרטים, ועל סמך $k$-יית התווים והמצב היא מחליטה מה לכתוב בכל אחד מהסרטים ולאן להזיז כל אחד מ-$k$ הראשים — כל ראש בנפרד. ההדגשה ש-$k$ קבוע מראש חשובה: $k$ אינו רשאי לגדול עם הקלט, ולכן הוא נבלע בקבועים.

דוגמה. מכונה דו-סרטית שמעתיקה את הקלט לסרט השני ואז סורקת את שני הסרטים בכיוונים מנוגדים — נראה אותה בסעיף הדוגמאות. אי-דוגמה. "מכונה שמקצה סרט לכל תו בקלט" איננה מכונה $k$-סרטית לשום $k$, מפני שמספר הסרטים תלוי בקלט.

הגדרה 3: מדדי הזמן והמקום

בהינתן מכונה $M$ וקלט $x\in\Sigma_M^*$:

• $time_M(x)$ — מספר ההפעלות של פונקציית המעברים בריצת $M$ על $x$.
• $space_M(x)$ — מספר התאים השונים שבהם $M$ כותבת במהלך ריצתה על $x$.

אינטואיציה והבחנות עדינות. אין דבר כזה "מספר הצעדים של מכונה"; יש רק מספר צעדים של מכונה על קלט מסוים. אם המכונה כתבה חמש פעמים באותו תא, זה נספר חמש פעמים בזמן ופעם אחת במקום. שימו לב גם למה לא נספר במקום: תאים שהקלט ההתחלתי יושב בהם והמכונה לא כתבה בהם, אינם נספרים [01:05:20]. מכאן שאם $M$ מקבלת מיד את $x$ בלי לקרוא אותו — $time_M(x)$ ו-$space_M(x)$ הם $1$ בלבד, גם אם $x$ ארוך.

מוסכמה נוספת [00:19:10]: מדדי היעילות נמדדים תמיד כפונקציה של אורך הקלט $|x|$, ואנחנו מתעניינים בסדרי גודל, לא בספירה מדויקת.

הגדרה 4: המכונה האוניברסלית $M_U$

$M_U$ היא המכונה שהא"ב שלה בינרי, המקיימת: לכל מכונה $M$ ולכל $x\in\Sigma_M^*$,

אינטואיציה. $M_U$ יודעת לקבל מכונה מבחוץ ולהריץ אותה. שימו לב שהיא מחזירה את הקידוד של הפלט ולא את הפלט עצמו — ולזה יש סיבה מדויקת. שאלה של סטודנטים [00:35:22]: למה לא להחזיר את הפלט? התשובה: $M_U$ היא מכונה אחת קבועה עם א"ב קבוע (בינרי), והיא צריכה לעבוד עבור מכונות בעלות א"ב שרירותי; אין לה שום דרך לכתוב תו מא"ב שהיא רואה בפעם הראשונה. במכונת הכרעה ההערה מתייתרת: שם $M_U$ פשוט מקבלת אם $M$ מקבלת ודוחה אם $M$ דוחה.

המימוש שראינו בחישוביות — מכונה רב-סרטית בעלת חמישה סרטים: סרט קלט, סרט מכונה, סרט עבודה, סרט מצב, וסרט אורך תו.

הגדרה 5: קונפיגורציה

בהינתן מכונה $M$ ומחרוזת $x\in\Sigma_M^*$, קונפיגורציה בריצת $M$ על $x$ מורכבת משלושה רכיבים:

1. המצב הנוכחי;
2. תוכן הסרט;
3. מיקום הראש הקורא־כותב.

אינטואיציה. קונפיגורציה היא בדיוק כל המידע שצריך כדי להמשיך ריצה מנקודה מסוימת: "אם אני מתחיל ריצה ואני רוצה שאתם תמשיכו אותה, מה עלי לתת לכם?" [01:13:16]. שימו לב מה אינו חלק מקונפיגורציה: ההיסטוריה. כיצד הגענו לכאן אינו רלוונטי להמשך, ולמכונה עצמה גם אין דרך לזכור זאת.

דוגמה לגבול ההגדרה (שאלת סטודנטית, [01:23:52]): למה לא די בתו הנוכחי? כי ייתכן שבהמשך הריצה הראש יזוז עשרה תאים ימינה, ואם אין לך את תוכן כל הסרט לא תדעי מה מחכה שם. זה בדיוק כמו להעביר מישהו באמצע ריצה של תוכנית ב-C: לא די בערכי המשתנים של השורה הנוכחית.

אי-דוגמה (שאלת סטודנט, [01:18:35]): מכונה יכולה להגיע פעמיים לאותו תוכן סרט בדיוק — למשל מכונה בסגנון אוטומט שסורקת מחרוזת בינרית ובודקת זוגיות של מספר האחדים אינה משנה את הסרט כלל. אבל אלה אינן אותה קונפיגורציה, מפני שהמצב ומיקום הראש שונים.

הגדרה 6: המחלקות $DTime$ ו-$DSpace$

לכל פונקציה $f:\mathbb{N}\to\mathbb{N}$:

אינטואיציה. בחישוביות $R$ הייתה "כל הבעיות שקיימת להן מכונה מכריעה". כאן מוסיפים דרישה שנייה על אותה מכונה: לא רק להכריע, אלא להכריע כשמשאב הזמן (או המקום) חסום על ידי $f$.

סדר הכמתים — נקודת הכישלון הקלאסית [01:22:31]: הקבוע $c$ נבחר אחרי המכונה ולפני הקלט. מותר לו להיות תלוי ב-$M$ ובפונקציה, ואסור לו להיות תלוי ב-$x$. כשכתוב $O(f)$ בהקשר של מדדי סיבוכיות — זו בדיוק המשמעות.

Abuse of notation [01:20:25]: כותבים $DTime(n^2)$ אף שפורמלית צריך להגדיר את הפונקציה $f(n)=n^2$ ואז לכתוב $DTime(f)$. זו הכתיבה המקובלת.

מקרה גבול. אפשר לדבר על $f(n)=\lceil\lg n\rceil$, אבל אז המכונה אפילו לא מספיקה לקרוא את כל הקלט; במכונה דטרמיניסטית שאמורה להכריע נכונה זה נדיר, ויופיע בעיקר בהקשרים מקורבים או הסתברותיים.

משפטים והוכחות

משפט 1: מחיר המעבר ממכונה רב-סרטית למכונה חד-סרטית

לכל מכונה רב-סרטית $M$ קיימת מכונה חד-סרטית $\hat{M}$ מעל אותו א"ב קלט/פלט, כך ש:

1. הסמנטיקות של $M$ ושל $\hat{M}$ שוות — הן מחשבות בדיוק אותו דבר;
2. לכל $x\in\Sigma_M^*$ מתקיים

הוכחה (הרעיון והחשבון במלואו).

הבנייה. מגדילים את א"ב העבודה כך שכל תא בסרט היחיד של $\hat{M}$ יחזיק $k$-ייה של תווים — תו אחד עבור כל אחד מ-$k$ סרטי $M$ — ובנוסף סימון של מיקומי $k$ הראשים. כך כל "פרוסה אנכית" של $k$ הסרטים של $M$ מיוצגת בתא אחד של $\hat{M}$.

הסימולציה של צעד בודד. כדי לסמלץ צעד אחד של $M$, המכונה $\hat{M}$ חייבת קודם כול לדעת מה $k$ הראשים קוראים; אך מיקומי הראשים מפוזרים לאורך הסרט, ולכן היא צריכה לסרוק את כל התוכן. אחרי שאספה את $k$ התווים היא מפעילה את $\delta$ במצב הפנימי שלה, וסורקת שוב כדי לכתוב את $k$ התווים החדשים ולהזיז את $k$ סימוני הראשים. בסך הכול נדרשים ארבעה סוויפים על כל התוכן עבור כל צעד של $M$ [00:29:52].

החשבון. אורך התוכן שיש לסרוק חסום על ידי הטווח שהראשים ביקרו בו, כלומר על ידי $space_M(x)$; ה-$+2$ הוא בגלל חריגה של תא אחד לכל צד. לכן כל צעד של $M$ עולה ל-$\hat{M}$ לכל היותר $4\cdot(space_M(x)+2)$ צעדים, ומכיוון ש-$M$ מבצעת $time_M(x)$ צעדים, סך הכול $4\cdot time_M(x)\cdot(space_M(x)+2)$.

המקום. $\hat{M}$ כותבת בדיוק על אותו טווח תאים שבו השתמשה $M$ (עד כדי חריגה של תא-שניים), אלא שכל תא "שמן" יותר. השומן הזה נבלע בגודל א"ב העבודה — כלומר בקבוע שאינו תלוי בקלט — ולכן מבחינת מספר התאים מדובר באותו סדר גודל: $O(space_M(x))$.

הערה: בהרצאה זה נאמר בקיצור — המרצה הפנה לסרטוני האנימציה מקורס חישוביות ואמר מפורשות שההוכחה שם היא "יותר רעיון מהוכחה פורמלית" [00:31:27]. הפירוט לעיל הוא מה שהיד-מנופפת עומדת מאחוריו.

מה חשוב לקרוא נכון בטענה (שאלה מצוינת של סטודנטית, [00:27:12]). האי-שוויון $time_{\hat{M}}\le O(time_M\cdot space_M)$ אינו אומר ש-$\hat{M}$ מהירה יותר. הוא אומר שהיא לא גרועה בהרבה מדי — הכפל ב-$space_M$ יכול להיות משמעותי ביותר. הדוגמה: שפת הפלינדרומים נכרעת בזמן ליניארי במכונה דו-סרטית ובזמן ריבועי במכונה חד-סרטית. כלומר המודל הרב-סרטי אינו מחזק אותנו מבחינה חישובית, אבל כן מחזק אותנו מבחינת יעילות.

מסקנה 1.1. מכיוון ש-$space_M(x)\le time_M(x)$ (משפט 3 להלן), נובע גם

כלומר הפער בזמן במעבר לחד-סרטית הוא לכל היותר ריבועי.

משפט 2: יעילות המכונה האוניברסלית הרב-סרטית

תהי $M$ מכונה ויהי $x\in\Sigma_M^*$. אז

כאשר האי-שוויון הימני בכל שורה תקף כאשר $M$ קוראת את כל הקלט שלה, וכל הקבועים המוסתרים אינם תלויים לא ב-$M$ ולא ב-$x$.

הוכחה — חשבון מפורש של הסימולציה.

שלב האתחול. $M_U$ מעתיקה את $\langle M\rangle$ לסרט המכונה, את $\langle x\rangle$ לסרט העבודה, את $\langle q_{start}\rangle$ לסרט המצב, וכותבת סדרת אפסים באורך $\lceil\lg|\Gamma_M|\rceil+1$ בסרט אורך התו. כל זה דורש מעבר אחד על הקלט, כלומר $O(|\langle M,x\rangle|)$ צעדים ו-$O(|\langle M,x\rangle|)$ תאים.

למה בכלל צריך את סרט אורך התו? [00:41:12] בסרט העבודה לא כתוב $x$ אלא הקידוד הבינרי של $x$. כדי לקרוא תו בודד, $M_U$ חייבת לדעת כמה ביטים מרכיבים קידוד של תו אחד; סדרת האפסים משמשת כמונה לאורך זה. (השם "סרט אורך תו" הוא קיצור; מדובר באורך קידוד התו.)

הסימולציה. על כל צעד ש-$M$ הייתה עושה בריצתה על $x$, $M_U$ קוראת את התו הנוכחי מסרט העבודה ואת המצב מסרט המצב, ואז סורקת את כל טבלת $\delta$ הכתובה בסרט המכונה כדי למצוא את המעבר המתאים. במקרה הגרוע היא עוברת על כל הטבלה, כלומר על $O(|\langle M\rangle|)$ תאים. אם $M$ עוצרת — $M_U$ עוצרת.

חשבון הזמן. אתחול פלוס $time_M(x)$ צעדים, שלכל אחד תקורה של $|\langle M\rangle|$:

מדוע הביטוי השמאלי בדרך כלל נבלע? אם $M$ קוראת את כל הקלט שלה אז $time_M(x)\ge|x|$, ולכן $|\langle M\rangle|\cdot time_M(x)\ \ge\ |\langle M\rangle|+|\langle x\rangle|$ עד כדי קבוע. חשוב: זה לא תמיד נכון — אצל מכונה שאינה קוראת את כל הקלט הביטוי הראשון עשוי לשלוט. המרצה תיקן את עצמו מפורשות ואמר שהמילה "זניח" כבדה מדי, ושהניסוח הנכון הוא "קטן לעומת השני" [00:45:00].

מדוע $|\langle M\rangle|$ אינו נבלע ב-$O$? [00:42:52] מפני ש-$M$ היא חלק מהקלט של $M_U$. קבוע מותר שיהיה תלוי במכונה שמריצים — כאן המכונה שמריצים היא $M_U$, ואילו $M$ משתנה. לכן אסור להסתיר את $|\langle M\rangle|$.

חשבון המקום. $M_U$ נוגעת באותו מספר תאים כמו $M$, אבל היא כותבת בביטים: לכל תו מא"ב $\Gamma_M$ דרושים $\lceil\lg|\Gamma_M|\rceil$ ביטים (כדי לקודד את כל המספרים מ-$1$ עד $|\Gamma_M|$). מכאן $\lg|\Gamma_M|\cdot space_M(x)$, ובתוספת האתחול מתקבל החסם המבוקש. הערך השלם העליון נבלע בסימון $O$. שימו לב שכאן, בניגוד לזמן, לא באמת הרווחנו — פשוט בלענו את אורך הקלט בתוך המקום.

מסקנה 2.1: מכונה אוניברסלית חד-סרטית

קיימת מכונה אוניברסלית חד-סרטית $\hat{M}_U$ כך שלכל $M$ ולכל $x\in\Sigma_M^*$:

ובחסם הגס יותר

הוכחה. הרכבה של שני המשפטים הקודמים. $M_U$ מומשה כמכונה רב-סרטית; לפי משפט 1, מכונה חד-סרטית שקולה לה רצה בזמן $O(time\cdot space)$ של הרב-סרטית ובאותו סדר גודל של מקום. מציבים את $time_{M_U}$ ואת $space_{M_U}$ ממשפט 2 ומקבלים בדיוק את הביטויים לעיל. $\blacksquare$

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

משפט 3: המקום חסום על ידי הזמן

תהי $M$ מכונה ויהי $x\in\Sigma_M^*$. אז

הוכחה (מלאה). נסמן $n=time_M(x)$, ונסמן ב-$A$ את קבוצת התאים שהמכונה כותבת בהם בריצתה על $x$. לפי הגדרה 3, $|A|=space_M(x)$, ובבירור $|\{1,2,\ldots,n\}|=n=time_M(x)$. מדובר, אם כן, באי-שוויון בין גדלים של שתי קבוצות; וכפי שהודגש בהרצאה [01:01:39], מאחורי כל אי-שוויון בין גדלים מסתתרת פונקציה חד-חד-ערכית.

נגדיר $\varphi:A\to\{1,2,\ldots,n\}$ כך: לכל תא $t\in A$, נגדיר $\varphi(t)$ להיות הצעד הראשון שבו $M$ כתבה ב-$t$.

$\varphi$ מוגדרת היטב: אם $t\in A$ אז לפי הגדרת $A$ קיים צעד שבו המכונה כתבה ב-$t$; קבוצת הצעדים האלה אינה ריקה וסופית, ולכן יש לה מינימום.

$\varphi$ חד-חד-ערכית: בכל צעד המכונה כותבת בתא אחד בדיוק. לכן אם $\varphi(t_1)=\varphi(t_2)=j$, אזי בצעד $j$ נכתב גם ב-$t_1$ וגם ב-$t_2$, ומכאן $t_1=t_2$.

קיום פונקציה חד-חד-ערכית מ-$A$ אל $\{1,\ldots,n\}$ גורר $|A|\le n$, כלומר $space_M(x)\le time_M(x)$. $\blacksquare$

הערה: בסיכום הצעד "ההתאמה מגדירה פונקציה חד-חד-ערכית" נכתב בשורה אחת. הנימוק שמאחוריו — שבכל צעד נכתב בדיוק תא אחד — הוא בדיוק המקום שבו ההוכחה נשענת על הגדרת $space$ כ"תאים שנכתבו", ולא כ"תאים שבוקרו".

האינטואיציה מאחורי המשפט. כל צעד שהמכונה עושה הוא כתיבה. לפעמים היא כותבת בתא שכבר כתבה בו — וזה נספר לי כצעד אך לא כמקום. לכן המקום אף פעם לא "מדביק" את הזמן.

משפט 4: בכיוון ההפוך אין חסם כלל

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

הוכחה (נגד-דוגמה). נגדיר מכונה $M$ שעל כל קלט רצה לנצח, כאשר הראש הקורא־כותב זז ימינה ושמאלה על אותם שני תאים ללא הפסקה. אז לכל $x$ מתקיים $space_M(x)=2$ בעוד $time_M(x)=\infty$. אף פונקציה $g$ לא תקיים $\infty\le g(2)$. $\blacksquare$

הערה מהדיון בכיתה [01:08:31]: תשובה של סטודנט שאמר רק "המכונה עלולה לא לעצור" אינה מספיקה. גם במשפט 3 ייתכן שהמכונה לא עוצרת, ושם החסם עדיין נכון (טריוויאלית). מה שהופך את הנגד-דוגמה הזו לתקפה הוא הצירוף: היא לא עוצרת וגם משתמשת במספר קבוע של תאים.

משפט 5: אם המכונה עוצרת — הזמן חסום אקספוננציאלית במקום

תהי $M$ מכונת טיורינג. אז קיים קבוע $c_M>0$ כך שלכל $x\in\Sigma_M^*$: אם $M$ עוצרת על $x$ אז

בכתיב מקוצר: $time_M(x)\le 2^{O(space_M(x))}$.

שימו לב לסדר הכמתים: תחילה $M$, אחר כך $c_M$, ורק אז $x$. לכן $c_M$ מותר שיהיה תלוי במכונה ואסור שיהיה תלוי בקלט.

הוכחה.

שלב א' — אם המכונה עוצרת, היא לא מבקרת פעמיים באותה קונפיגורציה. המכונה דטרמיניסטית: ברגע שידוע המצב, תוכן הסרט ומיקום הראש — הצעד הבא נקבע ביחידות. נניח בשלילה ש-$M$ בריצתה על $x$ הגיעה לקונפיגורציה $C$ בצעד $i$ ושוב לאותה $C$ בצעד $j>i$. הקונפיגורציה קובעת את כל ההמשך (ההיסטוריה אינה חלק ממנה, וגם למכונה אין אמצעי לזכור אותה), ולכן מצעד $j$ ואילך תחזור בדיוק אותה סדרת צעדים, ובצעד $j+(j-i)$ נגיע שוב ל-$C$ — וכן הלאה עד אינסוף. מכאן ש-$M$ לא תעצור, בסתירה. לכן:

אם $M$ עוצרת על $x$, אז $M$ עוברת בכל קונפיגורציה לכל היותר פעם אחת.

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

שלב ג' — ספירת הקונפיגורציות. קונפיגורציה מורכבת משלושה רכיבים בלתי תלויים:

• מצב: $|Q|$ אפשרויות.
• תוכן הסרט: אמנם הסרט אינסופי, אך התאים שמחוצה לטווח הריצה נשארים ריקים לנצח. בטווח יש $space_M(x)$ תאים, ולכל תא $|\Gamma|$ אפשרויות בלתי תלויות — מחרוזת באורך $s$ מעל א"ב בגודל $g$ נותנת $g^{s}$ אפשרויות. סך הכול $|\Gamma|^{space_M(x)}$.
• מיקום הראש: הראש אינו יכול לחרוג מהטווח שנכתב בו (בכל צעד הוא כותב), ולכן $space_M(x)$ אפשרויות.

לכן

שלב ד' — האלגברה: העברה לבסיס $2$. נסמן $s=space_M(x)$. נשתמש בזהות $a=2^{\lg a}$ ובכלל $a^{b}=2^{\,b\lg a}$:

נוציא את $s$ כגורם משותף בחזקה:

כעת נחסום מלמעלה. אם $s\ge 1$ אז $\frac{\lg|Q|}{s}\le\lg|Q|$, וכן $\frac{\lg s}{s}\le 1$ מפני ש-$\lg s\le s$ לכל $s\ge1$. לכן

נגדיר $c_M=\lg|Q|+\lg|\Gamma|+1$ ונקבל בדיוק את הנדרש. $\blacksquare$

הערה — התנאי $s\ge1$ מסומן בסיכום באדום. החלוקה ב-$s$ בשלב ד' אינה חוקית כאשר $space_M(x)=0$. המקרה הזה מטופל בנפרד וטריוויאלית: $space_M(x)=0$ פירושו שהמכונה לא כתבה באף תא, כלומר לא ביצעה אף צעד, ואז $time_M(x)=0\le 1=2^{c_M\cdot 0}$. בכל מקרה אחר המכונה ביצעה לפחות צעד אחד, ובכל צעד היא כותבת בתא, ולכן $space_M(x)\ge1$.

מה חשוב בביטוי שהתקבל. $c_M=\lg|Q|+\lg|\Gamma|+1$ תלוי רק במכונה — במספר המצבים ובגודל א"ב העבודה — ולא בקלט. זו כל הפואנטה. כמו כן החסם אינו הדוק: בשלב ד' העלמנו לתוך המכפלה איברים שיכלו להיות קטנים בהרבה. זה בסדר, מפני שכל מה שרצינו הוא הצורה $2^{O(space)}$.

משפט 6: $DTime(f)\subseteq DSpace(f)$

טענה. לכל $f:\mathbb{N}\to\mathbb{N}$ מתקיים $DTime(f)\subseteq DSpace(f)$.

הוכחה. תהי $f$ כלשהי ותהי $A\in DTime(f)$. לפי ההגדרה קיימת מכונה $M$ וקיים קבוע $c>0$ כך ש-$M$ מכריעה את $A$ ולכל $x\in\Sigma^*$ מתקיים $time_M(x)\le c\cdot f(|x|)$.

לפי משפט 3, לכל $x$ מתקיים $space_M(x)\le time_M(x)$. בשרשור:

כלומר אותה מכונה $M$ עצמה מכריעה את $A$ ומקיימת את מגבלת המקום עם אותו קבוע $c$, שאינו תלוי ב-$x$. לפי ההגדרה, $A\in DSpace(f)$. $\blacksquare$

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

משפט 7: $DSpace(f)\subseteq DTime\!\left(2^{O(f)}\right)$

סימון. הכתיב $DTime\!\left(2^{O(f)}\right)$ הוא קיצור לאיחוד

כלומר: קיים איזשהו קבוע $c$ שאינו תלוי בקלט, שעבורו הבעיה נכרעת בזמן $2^{c\cdot f}$. שימו לב שמסתתרים כאן שני קבועים — אחד מתוך ה-$O$ שבמעריך ואחד מהגדרת $DTime$ עצמה [01:33:10].

הוכחה. תהי $f$ כלשהי ותהי $A\in DSpace(f)$. לפי ההגדרה קיימת מכונה $M$ וקיים $c>0$ כך ש-$M$ מכריעה את $A$ ולכל $x$ מתקיים

שלב א' — למה $M$ עוצרת על כל קלט? זו נקודה עדינה שעלתה בכיתה [01:39:00]: חסם על המקום לבדו אינו מבטיח עצירה — ראו משפט 4. אבל כאן נתון יותר מזה: $M$ מכריעה את $A$, ומהגדרת ההכרעה, על קלט בשפה היא עוצרת ומקבלת ועל קלט מחוץ לשפה היא עוצרת ודוחה. לכן לכל $x$, $M$ עוצרת על $x$.

שלב ב' — הפעלת משפט 5. מכיוון ש-$M$ עוצרת על כל קלט, קיים $c'>0$ (התלוי ב-$M$ בלבד) כך שלכל $x$

שלב ג' — שרשור. נציב את חסם המקום בתוך המעריך:

שלב ד' — הגדרת הקבוע. נגדיר $d=c'\cdot c$. גם $c$ וגם $c'$ הם קבועים התלויים במכונה בלבד ואינם תלויים ב-$x$, ולכן גם $d$ כזה. קיבלנו מכונה $M$ המכריעה את $A$, ולכל $x$ מתקיים $time_M(x)\le 2^{\,d\cdot f(|x|)}$. לפי ההגדרה $A\in DTime\!\left(2^{\,d\cdot f}\right)\subseteq DTime\!\left(2^{O(f)}\right)$. $\blacksquare$

דוגמאות ותרגילים מהשיעור

דוגמה 1: שפת הפלינדרומים במכונה חד-סרטית — חשבון מלא

נגדיר

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

ספירת הצעדים. נסמן $n=|x|$. המעבר הראשון משמאל לימין עולה בערך $n$ צעדים; החזרה עולה בערך $n-1$; המעבר הבא $n-2$, וכן הלאה עד לצעד בודד. בסך הכול

זוהי סדרה חשבונית; אפשר לחשב את המספר המדויק, אבל אותנו מעניין סדר הגודל.

ספירת המקום. המכונה כותבת רק בתאים שבתוך הקלט (ואולי חורגת פעם אחת בתא אחד ימינה כדי לזהות את הסוף), ולכן $space=n+O(1)=O(n)$.

מסקנה. $PAL\in DTime(n^2)$ וגם $PAL\in DSpace(n)$. ההוכחה היא בדיוק בדיקת ההגדרה: הצגנו מכונה שמכריעה, ולכל $x$ הזמן שלה $O(|x|^2)$ והמקום שלה $O(|x|)$.

דוגמה 2: אותה שפה במכונה דו-סרטית — הרווח בזמן

האלגוריתם. שני הראשים מתחילים בתו השמאלי ביותר.

1. מעבר אחד משמאל לימין על שני הסרטים במקביל, שבו מעתיקים את כל $x$ מהסרט הראשון לסרט השני. עלות: $n$ צעדים.
2. מחזירים את הראש בסרט הראשון לתו השמאלי ביותר. עלות: $n$ צעדים.
3. מעבר מקבילי: הראש בסרט הראשון הולך ימינה, הראש בסרט השני הולך שמאלה (מהסוף להתחלה). בכל צעד משווים את שני התווים; אם אי-פעם הם שונים — דוחים. עלות: $n$ צעדים.

החשבון. בסך הכול כ-$3n$ צעדים, כלומר $time=O(n)$ — ליניארי, לא ריבועי. במקום, לעומת זאת, אנחנו משלמים קצת יותר: בכל צעד כותבים על שני תאים חדשים (אחד בכל סרט), כלומר בערך $2n+1$; אבל מאחר ש-$k=2$ קבוע מראש, זה עדיין $O(n)$.

התרגיל שנובע מזה. הריצו את משפט 1 על המכונה הזאת: המעבר לחד-סרטית עולה $O(time\cdot space)=O(n\cdot n)=O(n^2)$ — וקיבלנו בדיוק את המכונה החד-סרטית מדוגמה 1. זה מדגים ששני החסמים תופרים זה לזה בצורה הדוקה במקרה הזה.

דוגמה 3: המכונה שהמקום שלה $2$ והזמן שלה אינסוף

מכונה שכל מה שהיא עושה הוא להזיז את הראש ימינה, שמאלה, ימינה, שמאלה לנצח, ולכתוב בכל צעד באחד משני תאים. $space=2$, $time=\infty$. זו הנגד-דוגמה של משפט 4, והיא גם התשובה לשאלה "האם אי-העצירה היא כל הסיפור?" — התשובה, לפי משפט 5, היא כן: ברגע שמניחים עצירה, כן מתקבל חסם.

דוגמה 4 (תרגיל מהכיתה): מכונה שמקבלת מיד

נתונה מכונה שמקבלת כל קלט מיד, בלי לקרוא אותו. מהם המדדים שלה?

פתרון. $time=1$ ו-$space=1$. שימו לב שאורך הקלט אינו משפיע: התאים שהקלט יושב בהם לא נכתבו על ידי המכונה ולכן אינם נספרים במקום [01:05:20]. זו בדיוק ההבחנה שההגדרה של $space$ היא "תאים שנכתבו" ולא "תאים שקיימים".

תרגיל 5 (ספירה קומבינטורית, מהכיתה)

כמה מחרוזות שונות באורך $k$ יש מעל א"ב בגודל $m$?

פתרון. לכל אחד מ-$k$ המקומות יש $m$ אפשרויות, והבחירות בלתי תלויות, ולכן $m^{k}$. זה בדיוק הרכיב $|\Gamma|^{space_M(x)}$ בספירת הקונפיגורציות — נקודה שבלבלה כמה סטודנטים בשיעור, שחשבו שמדובר ב-$|\Gamma|\cdot space$ במקום בחזקה.

תרגיל 6 (הבנת ההגדרה): לאיזו מחלקה שייכת $PAL$?

פתרון. לפי דוגמה 1 (מכונה סטנדרטית, כמתחייב מהקונבנציה): $PAL\in DTime(n^2)$ ו-$PAL\in DSpace(n)$. מדגישים "סטנדרטית", שכן אילו מדדנו במכונה דו-סרטית היינו מקבלים $O(n)$ בזמן — וזו הסיבה שהקונבנציה נקבעה מראש.

בדיקת עקביות עם משפט 6 ומשפט 7. משפט 6 נותן $DTime(n^2)\subseteq DSpace(n^2)$, ואכן $O(n)\subseteq O(n^2)$ — עקבי, אם כי לא הדוק כאן. משפט 7 נותן $DSpace(n)\subseteq DTime(2^{O(n)})$, וגם זה מתקיים בבירור עבור מכונה שרצה בזמן $O(n^2)$.

הערות מהשיעור

• "יעיל" הוא מושג לא אבסולוטי [00:04:06]. בניגוד ל"ניתן/לא ניתן לחשב", שהוא מוחלט, יעילות היא "עניין של אופנה". כשהתחום התחיל בשנות ה-70 של המאה הקודמת, זמן ריצה פולינומי בגודל הקלט נחשב יעיל — אף שגם אז ידעו ש-$x^{100}$ אינו באמת יעיל [00:04:37]. היום, בגלל גדלי הנתונים, גם זמן ליניארי לא תמיד נחשב יעיל [00:05:08].
• אילו משאבים בכלל יש? [00:06:13]–[00:12:42] הדיון בכיתה העלה: זמן, מקום/זיכרון, רוחב פס (כמות הנתונים שצריך להעביר — קריטי באלגוריתמים מודרניים), ביטים אקראיים (יקרים, ו"הרנדום" של המחשב אינו באמת אקראי), ונאמנות/דיוק של האלגוריתם — אלגוריתם אקראי לפעמים טועה, וזה משאב שאני מוכן לסחור בו. בעולם האמיתי משתמשים במשאבים האלה "כמו פלסטלינה": משלמים בזמן כדי לקבל דיוק, משלמים במקום כדי לחסוך בזמן, מחשבים יותר בבית כדי לחסוך ברוחב פס.
• מה לא נספור [00:09:31]. זמן קומפילציה, זמן מתכנת, כמות שורות קוד — אלה משאבים אמיתיים בעולם האמיתי, אבל הם לא תלויים בקלט והם קורים לפני הריצה. בקורס הזה סופרים רק משאבים שנצרכים ב-run time.
• מה הקורס יכסה [00:09:09, בהקלטה השנייה]: (1) מה ניתן לחשב כשהמשאבים מוגבלים; (2) קשרים בין רמות הקושי של בעיות שונות, גם כשלא יודעים להכריע לגבי כל בעיה בנפרד; (3) מה עושים כשבעיה "קשה" — קירוב, אלגוריתמים הסתברותיים. בניגוד לחישוביות, כאן יודעים הרבה פחות: יש המון בעיות שלא יודעים לפתור ביעילות וגם לא יודעים להוכיח שאי אפשר.
• סימון $O$ מחביא דברים — דעו מה [00:26:08]. במעבר מרב-סרטית לחד-סרטית הקבועים המוסתרים תלויים במספר הסרטים. זה לא תלוי בקלט, אבל צריך להיות ברור מה בדיוק נבלע.
• "קטן שווה" אינו "יותר טוב" [00:28:13]. כשכותבים $\le$ לא אומרים "זה טוב יותר", אלא "זה לא הרבה יותר גרוע".
• המשפט הכי חוזר בשיעור [01:30:37], [00:52:11], [01:22:31]: כשאתם רואים $O(\cdot)$ בהקשר של מדדי סיבוכיות, שאלו את עצמכם במה הקבוע תלוי ובמה אינו תלוי. הוא אף פעם לא תלוי בקלט. "זה המקום שבו טועים" — נאמר מפורשות שלוש פעמים.
• מתי לא נכתוב יותר מכונות טיורינג [00:40:07]. "רוב הזמן בקורס הזה לא נכתוב מכונות טיורינג בצורה מפורשת, אנחנו נכתוב אותן כאלגוריתמים." כתבנו אותן בחישוביות כדי לקבל תחושה של המודל; קיבלנו את התחושה, אפשר להמשיך.
• על מספר הסרטים של המכונה האוניברסלית [00:38:33]. המרצה ציין שהוא "נדיב" בסרטים — שלושה או חמישה זה עד כדי קבוע, וקבוע כפלי אינו משחק תפקיד מספיק חשוב בתיאוריה הזאת. בעולם האמיתי ההבדל בין שלושה לחמישה כן חשוב.
• שאלת סטודנט ששווה לזכור [01:18:05]: "האם ייתכן שמכונה מיועדת להגיע לאותה קונפיגורציה כמה פעמים ורק אז לעצור?" התשובה — לא. ברגע שהיא לא יודעת את ההיסטוריה, היא לא יודעת שהיא כבר הייתה שם. אבל שימו לב לניסוח: אותו תוכן סרט יכול לחזור פעמיים; מה שלא יכול לחזור הוא השלישייה כולה.
• על כתיבה ביד [00:22:53]. המרצה מעלה את המחברת ואת ההקלטה, ובכל זאת המליץ לכתוב, לפחות את הטענות המרכזיות וההגדרות — "הזיכרון שלנו עובד יותר טוב כשזה עובר דרך היד", וגם כדי שהחומר יהיה מול העיניים כשמפנים אליו כעבור עשר דקות.
• תנאי הלמידה [00:53:37]: השיעור הופסק פעמיים באמצע בגלל אזעקות; הפסקה של רבע שעה. "תשמרו על עצמכם, זה יותר חשוב מסיבוכיות."
• המשימה לשיעור הבא [01:32:10]: לחזור על החשבון של שלב ד' במשפט 5 ולוודא שאתם יודעים לבצע אותו לבד — המניפולציות של לוגים וחזקות והמעבר ל-$2^{\lg(\cdot)}$ "צריכים לשבת ממש ממש טוב". זו אלגברה, לא סיבוכיות. בנוסף — למי שלא ראה, לצפות בסרטוני הסימולציה הרב-סרטית מקורס חישוביות.

פערים בין הסיכום להקלטה

• מקור: עמוד 1 בסיכום. הפער: מכונת טיורינג מוגדרת שם כחמישייה $M=(Q,F,\Sigma,\Gamma,\delta)$, ללא $q_{start}$; גם בהקלטה הראשונה המרצה התבלבל בהגדרה בזמן אמת [00:15:56] ותיקן את עצמו כמה פעמים. ההכרעה: בגוף השיעור כתבתי את ההגדרה עם $q_{start}$, מפני שהמכונה חייבת מצב התחלתי; ההקלטה השנייה [00:12:48] אכן מונה אותו במפורש כרכיב.
• מקור: ההקלטה השנייה בלבד, [01:13:29]–[01:43:19]. הפער: הגדרות $DTime(f)$ ו-$DSpace(f)$, שתי ההכלות ביניהן, והפירוק $DTime(2^{O(f)})=\bigcup_c DTime(2^{c f})$ — כל אלה אינם מופיעים כלל בארבעת עמודי הסיכום. ההכרעה: נכללו במלואם, שכן הם נלמדו בשיעור והם התוצר העיקרי שלו.
• מקור: ההקלטה הראשונה. הפער: ההקלטה הראשונה אינה מגיעה למחלקות; היא נעצרת בדיוק אחרי הטענה $time_M(x)\le 2^{c\cdot space_M(x)}$, ככל הנראה בגלל שתי הפסקות האזעקה. ההכרעה: שתי ההקלטות סומנו coverage: full מפני שיחד הן מכסות את השיעור, והשנייה מכסה גם את מה שהראשונה החמיצה.
• מקור: דוגמת הפלינדרומים. הפער: מופיעה בשתי ההקלטות (בהרחבה בשנייה, [00:16:32]–[00:20:14]) ואינה מופיעה בסיכום כלל. ההכרעה: נכללה בסעיף הדוגמאות עם החשבון המלא, כי היא הדוגמה היחידה בשיעור שבה מדדי הזמן והמקום מחושבים מקצה לקצה.
• מקור: עמוד 2 בסיכום מול ההקלטה השנייה [00:43:10]. הפער: הסיכום נותן למכונה האוניברסלית החד-סרטית חסם זמן במכפלה $O\big(|\langle M\rangle|\cdot time_M(x)\cdot\lg|\Gamma_M|\cdot space_M(x)\big)$, ואילו בהקלטה השנייה נאמר החסם הגס יותר $O\big(|\langle M\rangle|^2\cdot time_M(x)^2\big)$. ההכרעה: שני החסמים נכונים — השני מתקבל מהראשון על ידי הצבת $space\le time$ ו-$\lg|\Gamma_M|\le|\langle M\rangle|$ — והבאתי את גרסת הסיכום כעיקרית, כי היא ההדוקה יותר, עם המסקנה הריבועית כהערה.
• מקור: עמוד 2 בסיכום. הפער: חסם הזמן של המכונה האוניברסלית נכתב עם סימן שוויון: $time_{M_U}(\langle M,x\rangle)=O(\ldots)$. ההכרעה: מדובר בחסם עליון; שמרתי על הסימון של הסיכום בשורה הראשונה, אך ניסחתי את הטענה כחסם.
• מקור: עמוד 4 בסיכום, ההערה האדומה. הפער: ההערה מסומנת בצבע ובשני סימני קריאה אך ניסוחה המדויק בכתב היד קשה לפענוח מלא; ברור ממנה שהיא נוגעת לצורך להניח משהו על $space$ לפני החלוקה בשלב (*). ההכרעה: שוחזרה כתנאי $space_M(x)\ge1$ (שאחרת החלוקה אינה מוגדרת), והמקרה $space=0$ טופל בנפרד בגוף ההוכחה. זהו שחזור, לא קריאה מילולית.
• מקור: ההקלטה הראשונה, [01:04:19] ו-[01:20:11]. הפער: התמלול האוטומטי כותב "פונקציה חד ערכית" במקום "חד-חד-ערכית" (וגם "חדקית", "חדרכית"). ההכרעה: תוקן ל-injective; המשמעות המתמטית הנדרשת בשתי ההוכחות היא חד-חד-ערכיות, שהרי בלעדיה אין אי-שוויון בין גדלי הקבוצות.
• מקור: ההקלטה הראשונה, [00:24:59] ו-[01:26:32]. הפער: התמלול משבש כמעט כל סימון מתמטי — "טיים"/"ט" ל-$time$, "ספייס"/"ספיס"/"SP" ל-$space$, "לוגog"/"לogג" ל-$\lg$, "גמה"/"גם m" ל-$\Gamma_M$, "אמ כובע" ל-$\hat M$. ההכרעה: כל הסימונים אוחדו לפי הסיכום, שהוא המקור הסמכותי לנוטציה.
• מקור: ההקלטה הראשונה, [00:24:59]. הפער: המרצה אמר "בעיקרון זה היה ספייס $2$" ומיד תיקן ל"ועוד שתיים, זה בגלל החריגה לשני הצדדים". ההכרעה: הסיכום כותב $space_M(x)+2$, וזה הנוסח שנכלל; ההסבר לתוספת ($+1$ לכל צד) נכלל בגוף ההוכחה.
• מקור: משפט 1, שני המקורות. הפער: אף מקור אינו נותן הוכחה פורמלית לסימולציה הרב-סרטית; המרצה אמר במפורש שההוכחה בסרטונים "היא לא הוכחה פורמלית, היא יותר מה הרעיון" [00:31:58]. ההכרעה: כתבתי את הבנייה ואת חשבון ארבעת הסוויפים במלואם וסימנתי את הקטע בהערת "בהרצאה זה נאמר בקיצור".

סיכום ונקודות למבחן

מה חייבים לדעת בעל פה.

1. $time_M(x)$ — מספר הפעלות $\delta$. $space_M(x)$ — מספר התאים השונים שנכתבו. שתי המחרוזות "השונים" ו"שנכתבו" הן בדיוק הנקודות שנופלים בהן.
2. רב-סרטית $\to$ חד-סרטית: $time_{\hat M}\le 4\cdot time_M\cdot(space_M+2)=O(time_M\cdot space_M)\le O(time_M^2)$, והמקום נשמר עד כדי סדר גודל.
3. מכונה אוניברסלית: פקטור $|\langle M\rangle|$ בזמן, פקטור $\lg|\Gamma_M|$ במקום.
4. $space_M(x)\le time_M(x)$ — תמיד, ללא הנחות.
5. אין חסם הפוך בלי הנחת עצירה. עם הנחת עצירה: $time_M(x)\le 2^{c_M\cdot space_M(x)}$, כאשר $c_M=\lg|Q|+\lg|\Gamma|+1$.
6. מספר הקונפיגורציות $=|Q|\cdot|\Gamma|^{space}\cdot space$.
7. $DTime(f)\subseteq DSpace(f)\subseteq DTime\!\left(2^{O(f)}\right)$.

המלכודות הסטנדרטיות.

• סדר הכמתים. קבוע התלוי במכונה — מותר. קבוע התלוי בקלט — אסור. אם בהוכחה שלכם הקבוע "נבחר אחרי שראינו את $x$", ההוכחה שגויה.
• לחשוב ש-$\le$ פירושו "טוב יותר". במעבר לחד-סרטית האי-שוויון מבטיח רק ש"לא הרבה יותר גרוע".
• לענות "המכונה לא עוצרת" כנימוק שלם במשפט 4. חייבים גם לומר שהיא משתמשת במקום קבוע.
• לבלבל $|\Gamma|^{space}$ עם $|\Gamma|\cdot space$ בספירת הקונפיגורציות.
• לשכוח למה $M$ עוצרת בהוכחת משפט 7 — הנימוק אינו חסם המקום אלא העובדה שהיא מכריעה.
• לספור תאים שהקלט יושב בהם כחלק מה-$space$ כשהמכונה לא כתבה בהם.
• לשכוח את הקונבנציה שכל המדדים במכונה סטנדרטית חד-סרטית, אלא אם נאמר אחרת.

צ'ק-ליסט: מה סטודנט אמור לדעת לעשות אחרי השיעור.

• לחשב $time$ ו-$space$ של מכונה נתונה על קלט נתון, ולנמק כל אחד מהם.
• להוכיח שייכות של שפה ל-$DTime(f)$ או ל-$DSpace(f)$ על ידי הצגת מכונה ובדיקת שני התנאים בהגדרה.
• לבצע לבד את כל האלגברה של שלב ד' במשפט 5: $a^b=2^{b\lg a}$, איחוד חזקות, הוצאת $space$ כגורם משותף, והחסימות $\frac{\lg|Q|}{s}\le\lg|Q|$ ו-$\frac{\lg s}{s}\le1$.
• לספור קונפיגורציות של מכונה נתונה.
• לתרגם חסם על מכונה רב-סרטית לחסם על מכונה חד-סרטית ולהיפך.
• לזהות, בכל טענה עם $O$, במה הקבוע תלוי.

הסיכום הכתוב שעליו נשען הקובץ הוא של גיא סופר.