הבונה העסוק

בונה העסוק (Busy beaver) שואלת: כמה עבודה יכולה מכונת טיורינג עם n מצבים לעשות על סרט ריק לפני שהיא עוצרת. העבודה נמדדת בשני אופנים עיקריים: מספר הצעדים המקסימלי S(n), ומספר הסימנים 1 המקסימלי Σ(n).

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

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

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

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

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

אם יודעים לפתור את בעיית העצירה, ניתן לחשב S(n) ו-Σ(n) על ידי בדיקה אילו מכונות בתנאי n אכן עוצרות. להפך, מודעות לערכים של S או Σ מאפשרת לפתור את בעיית העצירה. לכן שתי הבעיות שקולות מבחינת חישוביות. המונח "אורקל" כאן מתאר מקור מידע חיצוני שאפשר לשאול לשאלות שאינן בהכרח חישוביות.

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

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

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

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

המכונה קוראת ומושכת את הסרט. היא פועלת לפי טבלת הוראות. יש לה מצבים פנימיים. לפעמים המכונה לעולם לא עוצרת.

S(n) אומרת את מספר הצעדים הכי גדול שמכונה עם n מצבים יכולה לבצע ואז לעצור. Σ(n) אומרת כמה סימני 1 הכי הרבה מכונה כזו יכולה להדפיס לפני שהיא עוצרת. לפעמים אין דרך כללית לחשב את הערכים האלה.

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

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

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