הצגת המקור של הדף "הבונה העסוק"

[[File:Busy Beaver 5 State 2 Color.png|thumb|300px|דיאגרמת זמן-מרחב שמדגימה את פעולתה של מכונת טיורינג. דיאגרמת המרחב-זמן של מכונה היא תמונה דו-ממדית שבה השורה ה-i מייצגת את סרט הזיכרון של המכונה באיטרציה ה-i. פיקסלים לבנים משמשים לתאי זיכרון המכילים 0 ופיקסלים כתומים מציינים את הערך 1. הדיאגרמה שבתמונה מדגימה את 100,000 הצעדים הראשונים של בעיית הבונה העסוק.<ref>{{Cite web |title=The Busy Beaver Challenge: Story # space-time-diagrams |url=https://bbchallenge.org/story#space-time-diagrams |access-date=2024-07-09 |website=bbchallenge.org |language=en}}</ref>]]'''הבונה העסוק''' (ב[[אנגלית]]: '''Busy beaver''') הוא שמה של בעיה לא [[כריעות|כריעה]] ב[[מדעי המחשב]], העוסקת בשאלה: "כמה עבודה ניתן לעשות באמצעות [[מכונת טיורינג]] עם מספר נתון של מצבים אפשריים, שפועלת על סרט ריק ועוצרת?".

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

==הקדמה==
===מכונת טיורינג===
{{הפניה לערך מורחב|מכונת טיורינג}}
אחת הדרכים לתאר באופן [[ריגורוזי]] פעולת [[אלגוריתם]] היא על ידי [[מכונת טיורינג]]. קיימות מספר הגדרות שקולות למושג "מכונת טיורינג". אחת הדרכים הפשוטות לראות את מכונת טיורינג היא על ידי המחשתה כמעין [[מחשב]] מכני בסיסי, שמורכב מארבעה חלקים:
*סרט אינסופי, עם התחלה, שעליו יכולות להיות כתובות [[סיבית|סיביות]] – [[0 (מספר)|אפסים]] או [[1 (מספר)|אחדות]] (בהקשר של בעיית הבונה העסוק, 0 בא לציין תא ריק; לרוב משתמשים בסימן מיוחד לשם כך).
*ראש לקריאה וכתיבה, שמונח על סיבית (תא) מסוים בסרט, ויכול לנוע [[ימין ושמאל (כיוונים במרחב)|ימינה או שמאלה]].
*רשימת מצבים פנימיים, שבהם המכונה יכולה להיות.
*טבלה של [[פקודה (מחשב)|הוראות]], שבה כל הוראה היא מהצורה: "כתוב X על הסרט במקום הסימן הקיים. עבור למצב הפנימי Y. לך ימינה/שמאלה עם הראש הקורא על גבי הסרט" או "עצור".
טבלת ההוראות היא בעצם ה[[תוכנה]] של המכונה. בטבלה זו כתוב למכונה מה לעשות אם היא נמצאת במצב מסוים, בהתאם לתוכן הסרט שהיא מסוגלת לראות באמצעות הראש. לדוגמה, עבור המכונה שבה יש שני מצבים, A ו-B, הטבלה הבאה היא אפשרות לטבלת הוראות עבור המכונה: 

{| class="wikitable" border="1"
|-
! מספר נקרא\מצב || A || B
|-
|style="text-align:center;"| 0 || כתוב 1, עבור למצב B, לך ימינה || כתוב 0, עבור למצב B, לך שמאלה
|-
|style="text-align:center;"| 1 || כתוב 1, עבור למצב A, לך ימינה || עצור
|}

בתחילת החישוב, המכונה נמצאת בתחילת הסרט, ולכן יכולה לנוע רק ימינה. נפעיל את המכונה המוצגת על ידי הטבלה על סרט שעליו כתובים רק אפסים, כאשר המצב ההתחלתי של המכונה הוא A:
# המכונה נמצאת במצב A עם קלט 0, ולכן לפי טבלת הפעולות, הראש הקורא יכתוב 1 בתא הראשון, יעבור תא אחד ימינה והמכונה תעבור למצב B. אחרי צעד זה, הסרט ייראה כך: ...1'''0'''00. (המקום שבו נמצא הראש הקורא מודגש.)
# המכונה נמצאת במצב B עם קלט 0, ולכן לפי טבלת הפעולות, הראש הקורא יכתוב 0 (כלומר לא ישנה את מה שכתוב), יישאר במצב B וילך שמאלה. אחרי צעד זה, הסרט יראה כך: ...'''1'''000.
# המכונה נמצאת במצב B עם קלט 1, ולכן לפי טבלת הפעולות המכונה תעצור.
[[פלט]] המכונה הוא כל התאים שמשמאל לראש הקורא – במקרה זה הראש נמצא בתא השמאלי ביותר, ולכן הפלט יהיה [[המילה הריקה]].

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

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

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

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

בהתאם לכך, מגדירים שתי פונקציות:
*<math>\ S(n)</math> – הפונקציה שסופרת את מספר הצעדים המקסימלי, שמכונה בת <math>n</math> מצבים יכולה לבצע על סרט ריק ו'''לעצור'''. העצירה היא חשובה ביותר, כיוון שלכל <math>n</math> קיימת מכונה שמבצעת אינסוף צעדים, כי היא פשוט לא עוצרת.
*<math>\ \Sigma (n)</math> – הפונקציה שסופרת את מספר האחדות המקסימלי, שמכונה בת <math>n</math> מצבים יכולה לכתוב על סרט ריק ולעצור.
פונקציות אלו אינן [[פונקציה רקורסיבית|רקורסיביות]], כי כדי לחשב אותן, יש לדעת איזו מכונה נעצרת ואיזו מכונה לא נעצרת – וזו [[בעיית העצירה]]. לכן, לא קיימת דרך לחשב אותן באופן כללי, אלא רק במקרים ספציפיים. מסיבה דומה, לא ניתן גם [[חסם עליון|לחסום מלמעלה]] באופן כללי את התקדמות הפונקציות על ידי פונקציה רקורסיבית, אלא אפשר רק לחשב [[חסם תחתון|חסמים תחתונים]]. עם זאת, ידועים ערכי הפונקציה עבור ערכים קטנים של <math>n</math>:
*עבור <math>n = 1</math> קל לראות ש- <math>\Sigma(1)=\ S(1)=1</math>.
*עבור <math>n = 2</math> מתקבל <math>\Sigma (2) =4 ,\ S(2)=6</math>.
*עבור <math>n = 3</math> מתקבל <math>\Sigma (3) =6 ,\ S(3)=21</math>
*עבור <math>n = 4</math> מתקבל <math>\Sigma (4) =13 ,\ S(4)=107</math>
*עבור <math>n = 5</math> מתקבל <math> \ S(5)=47176870</math>. תוצאה זו פורסמה ב-2.7.2024.<ref>{{קישור כללי|כתובת=https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237|כותרת=We have proved "BB(5) = 47,176,870"|אתר=The Busy Beaver Challenge|תאריך=2024-07-02|שפה=en|תאריך_וידוא=2024-07-13}}</ref>

==הוכחה ישירה לאי-הרקורסיביות של בעיית הבונה העסוק==
הרעיון הבסיסי ב[[הוכחה]] הוא [[הוכחה על דרך השלילה|להניח בשלילה]] שהפונקציות <math>\ S(n) , \ \Sigma (n)</math> ניתנות לחישוב על ידי מכונת טיורינג, ועל ידי יצירת מכונת טיורינג חדשה מאותה מכונה – לקבל [[סתירה (לוגיקה)|סתירה]] למקסימליות של ערכי הפונקציות; כלומר, המכונה החדשה תבצע יותר צעדים מפונקציית הצעדים או תכתוב יותר אחדות מפונקציית ספירת האחדות.
===הוכחה שפונקציית ספירת הצעדים לא רקורסיבית===
[[הוכחה בדרך השלילה|נניח בשלילה]] ש-<math>S</math> רקורסיבית; כלומר, קיימת מכונת טיורינג, "EvalS", שבהינתן סרט עם <math>n</math> אחדות עליו מחזירה סרט עם <math>\ S(n)</math> אחדות.

הרעיון: נבנה מכונה בעלת <math>\ S(n)</math> מצבים פנימיים שמחשבת את <math>\ S(m)</math>, ולאחר מכן, בהתאם לתוצאת החישוב, מבצעת יותר מ-<math>\ S(m)</math> צעדים. לא ניתן לבנות מכונה זו באמצעות "EvalS" לבדה, שכן "EvalS" מקבלת כקלט סדרה של <math>n</math> אחדות, ועל מכונה אחרת (שגם לה יש מספר כלשהו של מצבים פנימיים שבהם יש להתחשב) להדפיס את אותם האחדות.{{דרושה הבהרה|סיבה =}}

על כן, נבנה את המכונה הגדולה שלנו ממספר "מכונות עזר". פרט ל-"EvalS", נשתמש במכונות הבאות:
*"Double" – מכונה, שבהתקבל סרט עם <math>n</math> אחדות רצופים עליו, תחזיר סרט עם <math>2n</math> אחדות. כוחה של המכונה הזו בכך, שהיא מסוגלת לפעול על קלט מכל גודל <math>n</math> שהוא.
*"Clean" – מכונה, שמוחקת את רצף האחדות שנכתב לפניה על הסרט. במכונה הזו נשתמש כדי להבטיח, שנבצע יותר מ-<math>\ S(m)</math> צעדים.

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

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

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

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

==השקילות לבעיית העצירה==
מצד אחד הפונקציות <math>\ S(n)</math> ו-<math>\ \Sigma (n)</math> ניתנות לחישוב תוך שימוש בפתרון ל[[בעיית העצירה]]. זאת מכיוון, שעל ידי היכולת לפתור את בעיית העצירה, ניתן להכריע אילו מכונות בנות <math>n</math> מצבים יעצרו, ולחשב את מספר הצעדים שהן מבצעות ומספר האחדות שהן כותבות לפני שהן עוצרות. החישוב הזה הוא חישוב סופי, כי ידוע שהמכונות עוצרות, וישנו רק מספר סופי של מכונות בעלות <math>n</math> מצבים פנימיים. מצד שני, הפונקציות <math>\ S(n)</math> ו-<math>\ \Sigma (n)</math> מוגדרות עבור כל [[מספר טבעי]]; לכן, הן בעצמן יכולות לשמש כ[[אורקל (מדעי המחשב)|אורקל]] עבור חישוב בעיות אחרות. אורקל הוא מקור מידע חיצוני, ולא בהכרח רקורסיבי, שניתן לשלב במכונת טיורינג ולהיעזר בו בחישובים. בעזרת הפונקציות האלו ניתן לפתור את בעיית העצירה; כלומר, לקבוע עבור כל מכונת טיורינג וכל [[קלט]], האם היא עוצרת על אותו קלט או לא.
===פתרון בעיית העצירה מתוך פונקציית ספירת הצעדים===
בהינתן מכונת טיורינג <math>M</math> וקלט <math>k</math>, ניתן לחשב האם המכונה עוצרת על הקלט באמצעות האלגוריתם הרקורסיבי הבא:
* נניח ש-<math>M</math> היא מכונה בת <math>n</math> מצבים ונסמן ב-<math>N</math> את הסכום של מספר המצבים במכונה <math>M</math> וה[[מספר]] <math>2k</math>.
* נשאל את ה[[אורקל (מדעי המחשב)|אורקל]], שהוא פונקציית ספירת הצעדים של הבונה העסוק, "מהו <math>\ S(N)</math>?"
* נחשב את פעולת <math>M</math> על הקלט <math>k</math> במשך <math>\ S(N)</math> צעדים. אם המכונה לא עוצרת במהלך אותם צעדים – אזי היא לא עוצרת לעולם.
האלגוריתם פועל, כי על ידי תוספת של <math>2k</math> מצבים למצבי המכונה המקורית, ניתן ליצור מכונה בת <math>n</math> מצבים, שמקבלת כקלט סרט ריק, כותבת את הקלט "<math>k</math>" על הסרט, חוזרת לתחילת הסרט ומשם פועלת כמו המכונה המקורית <math>M</math>. למכונה זו בדיוק <math>N</math> מצבים, ומספר צעדיה של <math>M</math> חסום על ידי מספר הצעדים של המכונה החדשה (שמבצעת כל צעד אותו מבצעת <math>M</math>, ובנוסף מאתחלת את הסרט לקלט של <math>M</math>).

אפשר [[הכללה (מתמטיקה)|להכליל]] את התוצאה הזו במעט: אם <math>f</math> היא פונקציה שמקיימת <math>\ f(n) \ge S(n)</math> לכל <math>n</math> טבעי, אז ניתן לפתור בעזרת הפונקציה <math>f</math> את בעיית העצירה, כאשר דרך הפתרון זהה לזו שלמעלה – עבור מכונה בת <math>n</math> מצבים, נחשב את הפעולות שהמכונה מבצעת על הקלט <math>k</math> במשך <math>\ f(n+2k)</math> צעדים. אם המכונה לא עצרה במהלך אותם צעדים, אז בפרט, היא לא עצרה במשך <math>\ S(n+2k)</math> הצעדים הראשונים, ולכן, לפי הגדרת <math>S</math> כמספר הצעדים המקסימלי שמכונה יכולה לבצע ולעצור, המכונה לא עוצרת לעולם.

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

מתוך מכונה בת <math>n</math> מצבים אפשר לבנות מכונת ספירת צעדים, כך שבכל צעד שהמכונה המקורית עושה, המכונה החדשה תכתוב 1 ותזוז ימינה. נסמן את מספר המצבים של מכונת ספירת הצעדים ב-<math>k_n</math>. זוהי [[פונקציה רקורסיבית]]. מספר האחדות שהמכונה יכולה לכתוב לפני שהיא עוצרת חסום על ידי <math>\ \Sigma (k_n)</math>, כמו כל מכונה אחרת עם <math>k_n</math> מצבים, אך במקרה הזה, מספר האחדות המקסימלי שמכונה כזו כותבת (ועוצרת) הוא בדיוק <math>\ S(n)</math>; כלומר, <math>\Sigma (k_n)\ge S(n)</math> – ובוודאי ש-<math>\ \Sigma (k_n)</math> ניתנת לחישוב מתוך <math>\ \Sigma (n)</math>, ולכן בעיית העצירה ניתנת לחישוב בעזרת <math>\ \Sigma (n)</math>.
==הכללה==
ניתן להרחיב את הבעיה למכונות טיורינג בעלות <math>m</math> סימנים (הסימן הריק, 1,  . . ., <math>m</math>), בניגוד למכונות הרגילות בעלות שני הסימנים (הסימן הריק ו-1). בצורה הזו, מידת החופש של המכונה גדולה הרבה יותר, והיא יכולה להדפיס הרבה יותר סימנים או לבצע הרבה יותר צעדים, ולעצור.

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

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}
* {{יוטיוב|AKiA7JBgJdQ|שם=הסבר לקהל הרחב על הבעיה, ובפרט על חישוב S(5)|ערוץ=Up and Atom|אורך כולל=20:35|אורך=20:35}} {{באנגלית}}

==הערות שוליים==
{{הערות שוליים}}
{{בקרת זהויות}}

[[קטגוריה:בעיות חישוביות]]
[[קטגוריה:חישוביות]]
[[קטגוריה:פונקציות בעלות גידול על-מעריכי]]
[[קטגוריה:בעיות שאינן ניתנות לחישוב]]