הבונה העסוק

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

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

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

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

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

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

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

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

כדי לפתור את בעיית העצירה בעזרת , מספיק לחשב פונקציה שחוסמת את  מתוך , ואז נפתור בעזרתה את בעיית העצירה, כפי שמתואר בסעיף הקודם.
מתוך מכונה בת  מצבים אפשר לבנות מכונת ספירת צעדים, כך שבכל צעד שהמכונה המקורית עושה, המכונה החדשה תכתוב 1 ותזוז ימינה. נסמן את מספר המצבים של מכונת ספירת הצעדים ב-. זוהי פונקציה רקורסיבית. מספר האחדות שהמכונה יכולה לכתוב לפני שהיא עוצרת חסום על ידי , כמו כל מכונה אחרת עם  מצבים, אך במקרה הזה, מספר האחדות המקסימלי שמכונה כזו כותבת (ועוצרת) הוא בדיוק ; כלומר,  – ובוודאי ש- ניתנת לחישוב מתוך , ולכן בעיית העצירה ניתנת לחישוב בעזרת .

הכללה

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