הבונה העסוק

הבונה העסוק (Busy beaver) הוא שמה של בעיה לא כריעה במדעי המחשב, העוסקת בשאלה: "כמה עבודה ניתן לעשות באמצעות מכונת טיורינג עם מספר נתון של מצבים אפשריים, שפועלת על סרט ריק ועוצרת?".

שתי השאלות העיקריות בתחום זה הן: מהו המספר המרבי של צעדים שמכונת טיורינג עם $n$ מצבים יכולה לבצע לפני שהיא עוצרת? (מספר זה מסומן ב-$S(n)$), ומהי הכמות המרבית של סימנים שהיא יכולה להדפיס לפני שהיא עוצרת? (מספר זה מסומן ב-$\ \Sigma (n)$). שתי הפונקציות האלו, $S(n)$ ו-$\ \Sigma (n)$, אינן ניתנות לחישוב רקורסיבי, כי ניתן להכריע באמצעותן את בעיית העצירה. יתרה מזו, הן גדלות אסימפטוטית מהר יותר מכל פונקציה רקורסיבית.

הקדמה

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

ערך מורחב – מכונת טיורינג

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

• סרט אינסופי, עם התחלה, שעליו יכולות להיות כתובות סיביות – אפסים או אחדות (בהקשר של בעיית הבונה העסוק, 0 בא לציין תא ריק; לרוב משתמשים בסימן מיוחד לשם כך).
• ראש לקריאה וכתיבה, שמונח על סיבית (תא) מסוים בסרט, ויכול לנוע ימינה או שמאלה.
• רשימת מצבים פנימיים, שבהם המכונה יכולה להיות.
• טבלה של הוראות, שבה כל הוראה היא מהצורה: "כתוב X על הסרט במקום הסימן הקיים. עבור למצב הפנימי Y. לך ימינה/שמאלה עם הראש הקורא על גבי הסרט" או "עצור".

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

מספר נקרא\מצב	A	B
0	כתוב 1, עבור למצב B, לך ימינה	כתוב 0, עבור למצב B, לך שמאלה
1	כתוב 1, עבור למצב A, לך ימינה	עצור

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

1. המכונה נמצאת במצב A עם קלט 0, ולכן לפי טבלת הפעולות, הראש הקורא יכתוב 1 בתא הראשון, יעבור תא אחד ימינה והמכונה תעבור למצב B. אחרי צעד זה, הסרט ייראה כך: ...1000. (המקום שבו נמצא הראש הקורא מודגש.)
2. המכונה נמצאת במצב B עם קלט 0, ולכן לפי טבלת הפעולות, הראש הקורא יכתוב 0 (כלומר לא ישנה את מה שכתוב), יישאר במצב B וילך שמאלה. אחרי צעד זה, הסרט יראה כך: ...1000.
3. המכונה נמצאת במצב B עם קלט 1, ולכן לפי טבלת הפעולות המכונה תעצור.

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

מראש, נראה שהאפשרויות של מכונה כזו יהיו מאד מוגבלות, כיוון שההוראות האפשריות בטבלה הן מאד מעטות, אך ניתן להוכיח כי המכונה שקולה בכוחה למודלים חישוביים נוספים רבים, ומסוגלת לבצע כל מה שמחשב מסוגל לבצע. על פי תזת צ'רץ'-טיורינג, כל אלגוריתם סביר ניתן לחישוב בידי מכונה מתאימה. נשים לב, שמכונת טיורינג יכולה גם לא לעצור. לדוגמה, במכונה עם מצב אחד, A, שיש לה הוראה עבור הקלט 0: "כתוב 1, עבור למצב A, לך שמאלה", תמלא סרט שמכיל רק אפסים באחדות ולעולם לא תעצור.

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

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

הגדרת פונקציות הבונה העסוק

לכל מספר טבעי $n$, יש רק מספר סופי של מכונות טיורינג בעלות $n$ מצבים (לפי התיאור לעיל, $\ (4(n+1))^{2n}$). מכיוון שכך, אפשר לשאול: "כמה צעדים נדרשים מן המכונה העוצרת האחרונה, לפני שהיא עוצרת, ובפלט של איזו מכונה יש הכי הרבה סימני 1?".

בהתאם לכך, מגדירים שתי פונקציות:

• $\ S(n)$ – הפונקציה שסופרת את מספר הצעדים המקסימלי, שמכונה בת $n$ מצבים יכולה לבצע על סרט ריק ולעצור. העצירה היא חשובה ביותר, כיוון שלכל $n$ קיימת מכונה שמבצעת אינסוף צעדים, כי היא פשוט לא עוצרת.
• $\ \Sigma (n)$ – הפונקציה שסופרת את מספר האחדות המקסימלי, שמכונה בת $n$ מצבים יכולה לכתוב על סרט ריק ולעצור.

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

• עבור $n=1$ קל לראות ש- $\Sigma (1)=\ S(1)=1$.
• עבור $n=2$ מתקבל $\Sigma (2)=4,\ S(2)=6$.
• עבור $n=3$ מתקבל $\Sigma (3)=6,\ S(3)=21$
• עבור $n=4$ מתקבל $\Sigma (4)=13,\ S(4)=107$

הוכחה ישירה לאי-הרקורסיביות של בעיית הבונה העסוק

הרעיון הבסיסי בהוכחה הוא להניח בשלילה שהפונקציות $\ S(n),\ \Sigma (n)$ ניתנות לחישוב על ידי מכונת טיורינג, ועל ידי יצירת מכונת טיורינג חדשה מאותה מכונה – לקבל סתירה למקסימליות של ערכי הפונקציות; כלומר, המכונה החדשה תבצע יותר צעדים מפונקציית הצעדים או תכתוב יותר אחדות מפונקציית ספירת האחדות.

הוכחה שפונקציית ספירת הצעדים לא רקורסיבית

נניח בשלילה ש-$S$ רקורסיבית; כלומר, קיימת מכונת טיורינג, "EvalS", שבהינתן סרט עם $n$ אחדות עליו מחזירה סרט עם $\ S(n)$ אחדות.

הרעיון: נבנה מכונה בעלת $\ S(n)$ מצבים פנימיים שמחשבת את $\ S(m)$, ולאחר מכן, בהתאם לתוצאת החישוב, מבצעת יותר מ-$\ S(m)$ צעדים. לא ניתן לבנות מכונה זו באמצעות "EvalS" לבדה, שכן "EvalS" מקבלת כקלט סדרה של $n$ אחדות, ועל מכונה אחרת (שגם לה יש מספר כלשהו של מצבים פנימיים שבהם יש להתחשב) להדפיס את אותם האחדות.^{[דרושה הבהרה]}

על כן, נבנה את המכונה הגדולה שלנו ממספר "מכונות עזר". פרט ל-"EvalS", נשתמש במכונות הבאות:

• "Double" – מכונה, שבהתקבל סרט עם $n$ אחדות רצופים עליו, תחזיר סרט עם $2n$ אחדות. כוחה של המכונה הזו בכך, שהיא מסוגלת לפעול על קלט מכל גודל $n$ שהוא.
• "Clean" – מכונה, שמוחקת את רצף האחדות שנכתב לפניה על הסרט. במכונה הזו נשתמש כדי להבטיח, שנבצע יותר מ-$\ S(m)$ צעדים.

נסתכל על שרשור המכונות יחד: Double | EvalS | Clean (כלומר, "Double" פועלת ראשונה, ומיד עם סיום פעולתה מתחילה ריצת "EvalS", ומיד עם סיום פעולתה מתחילה ריצת "Clean"). השרשור הוא בעצמו מכונת טיורינג, ונסמן את מספר המצבים השונים שבה בתור $k$ (זהו סכום מספרי המצבים של Double, EvalS, Clean).

כמו כן, ניתן לבנות מכונה בת $k$ מצבים, שכותבת פשוט $k$ אחדות רצופות על הסרט (לדוגמה, בכל שלב המכונה תכתוב 1, תעבור למצב הבא בסדרה ותלך ימינה, ואחרי השלב ה-$k$ תעצור). נסתכל על המכונה בת $2k$ המצבים, שנוצרת מהשרשור של המכונה שיוצרת $k$ אחדות עם המכונה "Double|EvalS|Clean", ונסמן את המכונה החדשה ב-$M$. זוהי המכונה שגורמת לסתירה המבוקשת: מצד אחד, יש בה $2k$ מצבים ($2k$ הוא ה-$m$ שהזכרנו קודם), ולכן היא יכולה לבצע לכל היותר $S(2k)$ צעדים. מצד שני, בצורת הבנייה שלה הבטחנו שהיא תבצע יותר צעדים מזה:

• ראשית המכונה כותבת $k$ אחדות על הסרט, ולאחר מכן היא מכפילה אותם באמצעות "Double". שלב זה דורש $2k$ צעדים לפחות (שכן בתחילת ריצתה, לא היו כתובות אחדות על הסרט כלל, ובכל צעד ניתן לכתוב רק סימן בודד).
• לאחר מכן המכונה מפעילה את "EvalS" על $2k$, ומחשבת את $S(2k)$.
• לאחר מכן מופעלת "Clean" על הפלט של $S(2k)$ אחדות שכתוב על הסרט. מכיוון שכדי למחוק כל תו יש צורך בצעד אחד לפחות, בהכרח "Clean" מבצעת לפחות $S(2k)$ צעדים. מכיוון שקודם התבצעו $S(2k)$ צעדים, בהכרח $M$ מבצעת יותר מ-$S(2k)$ צעדים, בסתירה להגדרת $S$.

הוכחה שפונקציית ספירת האחדות לא רקורסיבית

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

כמו קודם, נניח בשלילה ש-$\Sigma$ ניתנת לחישוב, וניצור את המכונה "$\Sigma$Eval", שעבור רצף של $n$ אחדות על הסרט, מחזירה את הערך של $\ \Sigma (n)$. בנוסף, כמו קודם, נשתמש במכונה "Double", שמכפילה את מספר האחדות שהופיע לפניה על הסרט. נשרשר את המכונות Double | Eval$\Sigma$ | Increment ונקבל מכונת טיורינג חדשה, שנסמן ב-$k$ את מספר המצבים שלה.
תהי $M$ מכונת טיורינג, שעבור סרט ריק כותבת $k$ אחדות (דורש $k$ מצבים), מפעילה את "Double | Eval$\Sigma$ | Increment" (דורש עוד $k$ מצבים), ונבדוק כמה אחדות היא מפיקה. קל לראות שהיא יוצרת בדיוק $\ \Sigma (2k)+1$ אחדות ועוצרת; אבל זה עומד בסתירה להגדרת $\ \Sigma (n)$, שמוגדר להיות המספר המקסימלי של אחדות שמכונה בת $n$ מצבים מסוגלת ליצור מסרט ריק לעצור, ולכן, הנחת השלילה שגויה – כלומר, $\Sigma$ לא ניתנת לחישוב.

השקילות לבעיית העצירה

מצד אחד הפונקציות $\ S(n)$ ו-$\ \Sigma (n)$ ניתנות לחישוב תוך שימוש בפתרון לבעיית העצירה. זאת מכיוון, שעל ידי היכולת לפתור את בעיית העצירה, ניתן להכריע אילו מכונות בנות $n$ מצבים יעצרו, ולחשב את מספר הצעדים שהן מבצעות ומספר האחדות שהן כותבות לפני שהן עוצרות. החישוב הזה הוא חישוב סופי, כי ידוע שהמכונות עוצרות, וישנו רק מספר סופי של מכונות בעלות $n$ מצבים פנימיים. מצד שני, הפונקציות $\ S(n)$ ו-$\ \Sigma (n)$ מוגדרות עבור כל מספר טבעי; לכן, הן בעצמן יכולות לשמש כאורקל עבור חישוב בעיות אחרות. אורקל הוא מקור מידע חיצוני, ולא בהכרח רקורסיבי, שניתן לשלב במכונת טיורינג ולהיעזר בו בחישובים. בעזרת הפונקציות האלו ניתן לפתור את בעיית העצירה; כלומר, לקבוע עבור כל מכונת טיורינג וכל קלט, האם היא עוצרת על אותו קלט או לא.

פתרון בעיית העצירה מתוך פונקציית ספירת הצעדים

בהינתן מכונת טיורינג $M$ וקלט $k$, ניתן לחשב האם המכונה עוצרת על הקלט באמצעות האלגוריתם הרקורסיבי הבא:

• נניח ש-$M$ היא מכונה בת $n$ מצבים ונסמן ב-$N$ את הסכום של מספר המצבים במכונה $M$ והמספר $2k$.
• נשאל את האורקל, שהוא פונקציית ספירת הצעדים של הבונה העסוק, "מהו $\ S(N)$?"
• נחשב את פעולת $M$ על הקלט $k$ במשך $\ S(N)$ צעדים. אם המכונה לא עוצרת במהלך אותם צעדים – אזי היא לא עוצרת לעולם.

האלגוריתם פועל, כי על ידי תוספת של $2k$ מצבים למצבי המכונה המקורית, ניתן ליצור מכונה בת $n$ מצבים, שמקבלת כקלט סרט ריק, כותבת את הקלט "$k$" על הסרט, חוזרת לתחילת הסרט ומשם פועלת כמו המכונה המקורית $M$. למכונה זו בדיוק $N$ מצבים, ומספר צעדיה של $M$ חסום על ידי מספר הצעדים של המכונה החדשה (שמבצעת כל צעד אותו מבצעת $M$, ובנוסף מאתחלת את הסרט לקלט של $M$).

אפשר להכליל את התוצאה הזו במעט: אם $f$ היא פונקציה שמקיימת $\ f(n)\geq S(n)$ לכל $n$ טבעי, אז ניתן לפתור בעזרת הפונקציה $f$ את בעיית העצירה, כאשר דרך הפתרון זהה לזו שלמעלה – עבור מכונה בת $n$ מצבים, נחשב את הפעולות שהמכונה מבצעת על הקלט $k$ במשך $\ f(n+2k)$ צעדים. אם המכונה לא עצרה במהלך אותם צעדים, אז בפרט, היא לא עצרה במשך $\ S(n+2k)$ הצעדים הראשונים, ולכן, לפי הגדרת $S$ כמספר הצעדים המקסימלי שמכונה יכולה לבצע ולעצור, המכונה לא עוצרת לעולם.

חישוב בעיית העצירה מתוך פונקציית ספירת האחדות

כדי לפתור את בעיית העצירה בעזרת $\ \Sigma (n)$, מספיק לחשב פונקציה שחוסמת את $\ S(n)$ מתוך $\ \Sigma (n)$, ואז נפתור בעזרתה את בעיית העצירה, כפי שמתואר בסעיף הקודם.

מתוך מכונה בת $n$ מצבים אפשר לבנות מכונת ספירת צעדים, כך שבכל צעד שהמכונה המקורית עושה, המכונה החדשה תכתוב 1 ותזוז ימינה. נסמן את מספר המצבים של מכונת ספירת הצעדים ב-$k_{n}$. זוהי פונקציה רקורסיבית. מספר האחדות שהמכונה יכולה לכתוב לפני שהיא עוצרת חסום על ידי $\ \Sigma (k_{n})$, כמו כל מכונה אחרת עם $k_{n}$ מצבים, אך במקרה הזה, מספר האחדות המקסימלי שמכונה כזו כותבת (ועוצרת) הוא בדיוק $\ S(n)$; כלומר, $\Sigma (k_{n})\geq S(n)$ – ובוודאי ש-$\ \Sigma (k_{n})$ ניתנת לחישוב מתוך $\ \Sigma (n)$, ולכן בעיית העצירה ניתנת לחישוב בעזרת $\ \Sigma (n)$.

הכללה

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

את פונקציית ספירת הצעדים של מכונה עם $m$ סימנים ו-$n$ מצבים מסמנים ב- $\ S(n,m)$, ואת פונקציית ספירת הסימנים (שאינם הסימן הריק) מסמנים ב- $\ \Sigma (n,m)$. גם פונקציות אלו הן פונקציות לא רקורסיביות, והן מחשבות את בעיית העצירה באותה צורה כמו במכונות הרגילות, בעלות שני הסימנים.