למה זכרון שהוא פחות מלגלג הוא קבוע?

בפוסט קודם הזכרתי בחטף טענה בתורת הסיבוכיות שנשמעת מוזרה מעט במבט ראשון - שאם בעיה דורשת כמות נמוכה יחסית של זכרון לפתרונה, אך כזו שעדיין תלויה בגודל הקלט (ועל כן, כאשר הקלט גדל עוד ועוד גם הזכרון גדל עוד ועוד, “לאינסוף”), הרי שלמעשה ניתן לפתור אותה תוך שימוש בכמות קבועה של זכרון (בלי תלות בגודל הקלט), וחסל. ה”נמוכה יחסית” הייתה, מבחינה פורמלית, כל פונקציה שקטנה ממש אסימפטוטית מ-\( \lg\lg n \) (הכוונה בכך היא שניתן להקטין את היחס \( \frac{f\left(n\right)}{\lg\lg n} \) כרצוננו ככל שנגדיל את \( n \)).

בפוסט הזה אני רוצה להראות בדיוק מדוע זה כך. ההוכחה אינה קלה במיוחד, אך היא משתמשת ברעיונות שכולם סטנדרטיים יחסית בתורת הסיבוכיות ולכן היא מספקת תירוץ טוב להציג אותם. הרעיון הבסיסי הוא שמכונה שמשתמשת רק בכמות עלובה כל כך של זכרון אינה מסוגלת לעשות כמעט שום דבר מעניין - בפרט, היא לא יכולה להשתמש ברוב הזכרון שעומד לרשותה כי אז היא “תתבלבל” ותנצל כמות גדולה הרבה יותר שלו. באופן טיפה יותר פורמלי מה שעושים הוא לקחת מכונה \( M \) שפועלת בסיבוכיות זכרון \( f\left(n\right) \) קטנה כמתואר לעיל, ולתת באופן כמעט מפורש חסם קבוע (שאינו תלוי ב-\( n \)) על כמות הזכרון שהמכונה תצרוך באמת בכל ריצה שלה. כדי להשתכנע שהחסם עובד, פועלים בדרך השלילה - מניחים שיש קלטים שעליהם המכונה חורגת מהחסם, לוקחים את המינימלי שבהם, ומראים שאפשר לקצר גם אותו ועדיין לקבל קלט שעליו המכונה חורגת מהחסם - סתירה למינימליות. עיקר החוכמה כאן היא איך מראים שאפשר לקצר את הקלט - זה דורש ניתוח מדוקדק יחסית של התנהגות המכונה על כל ביט בקלט והדגמה שקיימים שני ביטים שהם “זהים” מבחינת התנהגות המכונה עליהם, ניתוח שהוא טכני באופן בלתי נמנע.

התוצאה הזו היא אחד מהמקומות שבהם יש חשיבות גדולה למודל הספציפי של החישוב שאנחנו בוחרים - עבור מודל אחר ככל הנראה הפונקציה היתה שונה (במודלים “מתוחכמים” יותר אפשר להסתיר פעולות בעלות סיבוכיות לא קבועה תחת מעטה של “פעולה אטומית”). לכן אתאר בקצרה את המודל שלנו - מכונת טיורינג היא יצור שמורכב מסרט קלט (הניתן לקריאה בלבד), סרט עבודה לקריאה ולכתיבה, ראש קורא שנע על סרט הקלט, ראש קורא/כותב שנע על סרט העבודה, ואוסף \( Q \) של “מצבים פנימיים”, שהמכונה נמצאת כל רגע באחד מהם. המכונה פועלת ב”צעדים”, כאשר ההתנהגות בכל צעד נקבעת על פי המצב הפנימי של המכונה ותוכן התאים ששני הראשים קוראים; ובכל צעד המכונה יכולה לשנות את המצב הפנימי שלה, לכתוב תו על סרט העבודה במקום התו שהיה קודם במקום שעליו הראש הצביע, ולהזיז כל אחד מהראשים צעד אחד ימינה או שמאלה (הם בלתי תלויים זה בזה). זה הכל. בניסוחים נאיביים בדרך כלל לא טורחים לתת למכונה שני סרטים, וסרט הקלט משמש גם לקריאה וגם לכתיבה; אבל מכיוון שאנחנו עוסקים כאן בסיבוכיות זכרון שקטנה בהרבה מגודל הקלט, ההפרדה בין הזכרון של הקלט והזכרון שעליו כותבים היא הכרחית.

כעת הגיע הזמן להציג את המושג המרכזי בהוכחה (ומושג חשוב באופן כללי בתורת הסיבוכיות) - ה”קונפיגורציה” של המכונה (תרגום לעברית יכול להיות “תיאור רגעי”, אבל אני מעדיף את הלועזית כאן). גם כאן אתן הגדרה שתפורה עבור ההוכחה הזו, ואינה זהה לחלוטין להגדרה הסטנדרטית. קונפיגורציה של מכונה באה לתאר את מצבה הרגעי במהלך חישוב, ומורכבת מתוכן סרט העבודה (“הסרט כרגע מכיל את המחרוזת 01001”), מיקום הראש הקורא/כותב עליו (“הראש כרגע מעל תא מספר 3”), התוכן של התא שהראש הקורא נמצא מעליו כרגע (“אני קורא את הביט 1”) והמצב הפנימי הנוכחי של המכונה (“המכונה במצב פנימי מספר 17”). האבחנה המרכזית הנוגעת לקונפיגורציות היא שאם המכונה נמצאת באותה קונפיגורציה פעמיים במהלך החישוב שלה, כשבנוסף לכך בשתי הפעמים הללו הראש הקורא נמצא מעל אותו תא - פירוש הדבר הוא שהיא בלולאה אינסופית. מדוע? כי הקונפיגורציה הנוכחית, בתוספת מיקום הראש הקורא, קובעות בצורה יחידה ודטרמיניסטית את התנהגות המכונה בצעד הבא, ובפרט את הקונפיגורציה הבאה (והמיקום הבא של הראש הקורא). חשבו על תוכנית מחשב שמגיעה פעמיים לאותה שורת קוד, כשמצב כל המשתנים בתוכנית זהה בין שתי הפעמים - אם היא הגיעה משורה 17 שוב אל שורה 17 מבלי שכלום השתנה, אז בגלל הדטרמיניזם של אופן פעולתה, היא שוב תגיע לשורה 17 מבלי לשנות שום דבר, ושוב ושוב עד אין קץ.

נניח שהמכונה שלנו רצה על קלט מאורך \( n \), ולכן היא יכולה להשתמש לכל היותר ב-\( f\left(n\right) \) תאים של זכרון העבודה. כמה קונפיגורציות שונות אפשריות קיימות עבורה? לצורך העניין נניח שסרט העבודה מכיל רק ביטים, אז יש \( 2^{f\left(n\right)} \) אפשרויות שונות לתוכן סרט העבודה (קומבינטוריקה פשוטה: לכל אחד מ-\( f\left(n\right) \) התאים יש לנו שתי אפשרויות, 0 או 1, וכל תא נקבע באופן בלתי תלוי באחרים). כמו כן יש \( f\left(n\right) \) אפשרויות למיקום הראש הקורא/כותב, 2 אפשרויות לתוכן התא שהראש הקורא קורא ו-\( \left|Q\right| \)מצבים פנימיים אפשריים (זה מספר קבוע שאינו תלוי ב-\( n \) ולכן אינו כה מעניין). סה”כ יש \( t\left(n\right)=2\cdot\left|Q\right|\cdot f\left(n\right)\cdot2^{f\left(n\right)}=O\left(2^{f\left(n\right)}\right) \) קונפיגורציות אפשריות. אם כן, אם הראש הקורא של המכונה מבקר בתא כלשהו בסרט הקלט יותר מ-\( t\left(n\right) \) פעמיים, המכונה נכנסה ללולאה אינסופית, כי היינו באותה קונפיגורציה פעמיים בעת שהראש הקורא היה באותו תא (למה היינו באותה קונפיגורציה פעמיים? עקרון שובך היונים).

כעת מגיע אחד מהרעיונות המורכבים ביותר בהוכחה. לכל תא בסרט הקלט, נבנה רשימה של כל הקונפיגורציות שבהן המכונה הייתה בשעה שהיא ביקרה בתא הזה. למשל, הרשימה “11,53,23” עבור תא מס’ 3 אומרת שבפעם הראשונה שבה המכונה הגיעה לתא מס’ 3, היא הייתה בקונפיגורציה 11, ובפעם השניה שבה היא הגיעה לתא מס’ 3 (אולי אלפי צעדים לאחר מכן) היא הייתה בקונפיגורציה 53; ובפעם השלישית - בואו נניח שהיא הייתה מייד לאחר הפעם השניה, כי הראש הקורא לא זז - היא שינתה משהו בסרט העבודה שלה ועברה לקונפיגורציה 23. המספרים מומצאים, כמובן, אבל זה הרעיון. השאלה המהותית כאן היא מה האורך האפשרי של הרשימה הזו? התשובה פשוטה, ונעוצה במה שאמרתי לפני שנייה: אם הרשימה (עבור תא כלשהו) תכיל יותר מ-\( t\left(n\right) \) איברים, פירוש הדבר שהמכונה בלולאה אינסופית ולכן הרשימה תתחיל לחזור על עצמה לאחר מכן. מכאן שיש בסך הכל \( t\left(n\right)^{t\left(n\right)} \) סדרות אפשריות שכאלו של קונפיגורציות (כי אמרנו שיש לכל היותר \( t\left(n\right) \) איברים בסדרה, ו”איבר” יכול להיות כל אחת מ-\( t\left(n\right) \) הקונפיגורציות החוקיות). מסובך? כן, בהחלט; רצוי לקרוא את זה כמה פעמים (וגם אם לא מבינים, זה לא סוף העולם).

אנחנו חותרים להראות שעבור ריצות “בעייתיות” לכאורה עבורנו, נצליח למצוא כמה וכמה תאים בסרט הקלט שסדרת הקונפיגורציות שלהן תהיה זהה (ולכן התנהגות המכונה עליהן תהיה זהה). לשם כך אנחנו רוצים למצוא \( n \)-ים שעבורם יש יחסית מעט סדרות של קונפיגורציות, ויחסית הרבה תאי קלט - למעשה, פי שלוש מאשר סדרות של קונפיגורציות. זה נשמע מופרך - הרי יש \( n \) תאי קלט, אבל \( t\left(n\right)^{t\left(n\right)} \) סדרות; והרי פונקציות אקספוננציאליות גדלות מהר מאוד - אם כן, איך ייתכן שיהיה \( n \) שעבורו \( t\left(n\right)^{t\left(n\right)}<n \)? התשובה פשוטה - אל תשכחו ש-\( f\left(n\right) \), סיבוכיות הזכרון שלנו, היא קטנה מאוד, הרבה הרבה הרבה יותר קטנה מ-\( n \); זה בדיוק הרעיון כאן, וזה גם המקום שממנו החסם על \( f\left(n\right) \) מגיע. אם \( f\left(n\right)=o\left(\lg\lg n\right) \), אז מתקיים ש-\( t\left(n\right)^{t\left(n\right)}=o\left(n\right) \), כלומר קיים \( n_{0} \) גדול דיו כך שלכל \( n>n_{0} \) מתקיים \( t\left(n\right)^{t\left(n\right)}<\frac{n}{3} \). אני לא אכנס כאן לפרטי ההוכחה שהם טכניים ולא מעניינים - ה”אינטואיציה” היא שהחלק הדומיננטי ביותר ב-\( t\left(n\right)^{t\left(n\right)} \) הוא מהצורה \( 2^{2^{f\left(n\right)}} \), ושתי החזקות הללו “נאכלות” בידי הלוגריתם הכפול (כלומר: \( 2^{2^{f\left(n\right)}}=o\left(2^{2^{\lg\lg n}}\right)=o\left(2^{\lg n}\right)=o\left(n\right) \)).

כעת הגענו לטענה המרכזית שלנו - המכונה לא משתמשת ביותר מאשר \( f\left(n_{0}\right) \) זכרון בכלל, על כל קלט. מכיוון ש-\( n_{0} \) הוא קבוע (ואפילו הראינו דרך יחסית קונסטרוקטיבית למצוא אותו), גם \( f\left(n_{0}\right) \) הוא קבוע, ולכן הטענה הזו מסיימת את ההוכחה. כדי להראות אותה, נניח בשלילה שהיא איננה נכונה וניקח את הקלט \( x \) בעל האורך המינימלי שעדיין גדול מ-\( n_{0} \) (כלומר, \( \left|x\right|=n>n_{0} \)) שבריצתה עליו המכונה משתמשת ביותר מ-\( f\left(n_{0}\right) \) זכרון. מה שנראה הוא שניתן להקטין את \( x \) ולקבל קלט אחר, \( x^{\prime} \), שעליו המכונה מתנהגת באופן זהה, ולכן גם מנצלת את אותה כמות זכרון, וזוהי סתירה למינימליות \( x \). במילים אחרות - אנחנו מראים שעל קלטים ארוכים מספיק, המכונה מתנהגת באופן זהה לזה שבו היא מתנהגת על קלטים קצרים יותר - ולכן צריכת הזיכרון שלה היא לא יותר מאשר צריכת הזיכרון המקסימלית של המכונה על אחד מאותם קלטים קצרים. מכיוון שיש מספר סופי של קלטים קצרים שכזה, צריכת הזכרון המקסימלית הזו היא מספר קבוע.

כעת נעבור לפאנץ’ שמסביר את קיום מספר הקסם המסתורי \( \frac{n}{3} \). מכיוון ש-\( \left|x\right|=n>n_{0} \) אז \( t\left(n\right)^{t\left(n\right)}<\frac{n}{3} \). ובמילים - מספר סדרות הקונפיגורציות האפשריות הוא פחות משליש ממספר תאי הזכרון. מכאן נובע שיש לפחות שלושה תאי זכרון עם אותה סדרת קונפיגורציות בדיוק. נניח שהתוכן שלהם הוא 0 (עבור תוכן של 1 ההוכחה היא אותו דבר), אז ניתן לתאר את הקלט כולו כך: \( x=\alpha0\beta0\gamma0\delta \), כש-\( \alpha,\beta,\gamma,\delta \) הם פשוט סימונים לתת-מחרוזות. כן, אני יודע שזה נראה קצת מפחיד.

מה שאני רוצה להראות הוא שגם אם אקצץ את \( \beta0 \) מהמחרוזת הזו ואקבל \( x^{\prime}=\alpha0\gamma0\delta \), ההתנהגות של המכונה על הקלט תהיה זהה (חוץ מההתנהגות שלה על הקטע \( \beta \) שכבר אינו קיים). כמקודם, זה טכני ואעדיף שלא לחפור יותר מדי בפרטים, אבל הנה הרעיון הכללי: כל עוד המכונה (שמתחילה לעבור על הקלט מצד שמאל) מתרוצצת על החלק של \( \alpha \) ברור שההתנהגות שלה זהה הן עבור \( x \) והן עבור \( x^{\prime} \). בכל פעם שהיא מגיעה ל-0 הראשון היא עשויה או לפנות שמאלה, או ימינה. אם היא פונה שמאלה היא ממשיכה להתעסק באיזור ה-\( \alpha \); כשהיא פונה ימינה לראשונה, נניח בביקור ה-\( i \), זה יהיה כך הן עבור \( x \) והן עבור \( x^{\prime} \) - המכונה תהיה באותה קונפיגורציה. כעת ריצת המכונה על \( x \) מגיעה לאיזור של \( \beta \) ומי יודע מה קורה שם, אבל דבר אחד ברור - בכל פעם שהיא מגיעה אל ה-\( 0 \) שמימין לאותו \( \beta \), היא תפנה שמאלה, עד הפעם ה-\( i \) בדיוק - וזאת בגלל שסדרת הקונפיגורציות של ה-\( 0 \) שליד \( \alpha \) וה-\( 0 \) שליד \( \beta \) זהה, ולכן ההתנהגות של המכונה שם היא זהה.

כלומר, בפעם הראשונה שבה המכונה תפנה ימינה ב-\( 0 \) שאחרי ה-\( \beta \) זה יהיה בביקור ה-\( i \) של המכונה שם - כלומר, כשהיא נמצאת באותה קונפיגורציה בדיוק כמו המכונה בריצתה על \( x^{\prime} \) כשהיא פנתה ימינה בביקור ה-\( i \) שלה על ה-\( 0 \) שליד \( \alpha \)… אני מקווה שהבנתם את הרעיון. אם לא, נסו לשחק את המשחק בעצמכם קצת - זו כנראה הדרך היחידה להבין עד הסוף, שאינה טרוחה בהוכחה ארוכה וטרחנית. אם טרם הבנתם, קחו את המילה שלי לגבי העניין הזה.

באופן דומה אפשר להראות שגם על \( x^{\prime\prime}=\alpha0\beta0\delta \) המכונה מתנהגת כמו שהיא מתנהגת על \( x \). כעת אפשר להגיע לפאנץ’ הסופי. אנחנו יודעים שלצריכת הזיכרון המקסימלית שלה המכונה מגיעה כשהיא על תו כלשהו מהקלט, אבל איזה תו? אם הוא ב-\( \alpha \), או ב-\( \gamma \), או ב-\( \delta \), או ב-\( 0 \) שליד \( \alpha \), או ב-\( 0 \) שליד \( \gamma \) - בכל אחד מהמקרים הללו, התו הזה קיים גם ב-\( x^{\prime} \) והמכונה מתנהגת עליו באותו אופן - כלומר, המכונה מגיעה לצריכת הזכרון המקסימלית שלה גם על \( x^{\prime} \) הקטן מ-\( x \). ואם צריכת הזכרון המקסימלית היא ב-\( \beta \) או ב-\( 0 \) שלידו, אז היא מגיעה אליו ב-\( x^{\prime\prime} \) הקטן יותר מ-\( x \). זו הסיבה שנזקקנו הן ל-\( x^{\prime} \) והן ל-\( x^{\prime\prime} \) - כדי למנוע את המצב המעצבן שבו צריכת הזכרון המקסימלית היא דווקא בתוך החלק מהמילה שאנחנו מקצצים.

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