בעיות מפורסמות במדעי המחשב

The Busy Beaver Problem

בעיה בתחום התיאורטי של מכונת טיורינג

הכנה: נוע רגוניס, מכון ויצמן למדע

ניתן להשתמש בחומרים לצורך הוראת הנושא לתלמידי תיכון.

לא ניתן לעשות בחומר כל שימוש מסחרי ללא רשות בכתב מראש מיוצרי החומרים.

 

תיאור הבעיה

בתחילת המאה הקודמת, בשנת 1900, הציג דיוויד הילברט (David Hilbert) רשימה של 23 בעיות מתמטיות חשובות שלא נפתרו עד זמנו. הילברט סבר שהפתרון של בעיות אלו יאפשר לבסס את כל המתמטיקה על אקסיומות, כך שיהיה ניתן לבדוק תקפות של כל משפט. הפרויקט נכשל לאחר שקורט גדל (Kurt Gödel) הוכיח כי לחלק מן השאלות לא נמצא פתרון. אולם לפתרון אחת הבעיות אותה נתאר כאן יש השלכה חשובה על מדעי המחשב. כהרחבה לקובץ השאלות המקורי, פרסם הילברט בשנת 1928 את הבעיה הבאה: האם אפשרי להחליט עבור כל טענה מתמטית האם היא נכונה או לא. למרות שהילברט התייחס למציאת פרוצדורה "מכנית", טיורינג החליט להשתמש במושג המתמטי של חישוב במונח המילולי ולבנות מכונה. התרגום של טיורינג לבעיה שהציג הילברט היא בעית העצירה, אותה ניסח כך:

בעיית העצירה: בהינתן למכונת טיורינג קלט שהוא מכונת טיורינג M כלשהי עם סרט ריק, הפלט יהיה תשובה לשאלה "האם המכונה M עוצרת או לא?"

 

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

 

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

כללי

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

מבנה המכונה

מכונת טיורינג מורכבת מהרכיבים הבאים:

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

*  ראש שמסוגל לקרוא ולכתוב את תוכנו של תא, ולזוז ימינה או שמאלה לאורך הסרט.

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

תיאור אלגוריתם לביצוע על ידי המכונה

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

(מצב חדש, כיוון תנועת הראש, אות לכתיבה בתא הנוכחי)  ® (אות המופיעה בתא הנוכחי, מצב נוכחי)

למשל,

פירושו: כאשר המכונה נמצאת במצב q2 ובתא שעליו נמצא הראש של המכונה כתובה האות a, אזי יש לכתוב בתא הנוכחי את האות b, הראש צריך לנוע ימינה (Right) והמצב החדש של המכונה המתעדכן באוגר המצב הוא q3.

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

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

בעיית ה- Busy Beaver

בעיית העצירה של מכונת טיורינג

בעיית העצירה: בהינתן למכונת טיורינג קלט שהוא מכונת טיורינג M כלשהי עם סרט ריק, הפלט יהיה תשובה לשאלה "האם המכונה M עוצרת או לא?"

 

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

בעיית העצירה הכללית מוגדרת באופן הבא:

בעיית העצירה הכללית:

האם קיים אלגוריתם המקבל כקלט אלגוריתם אחר ואת רשימת הקלט לאלגוריתם זה

ונותן תשובה האם האלגוריתם שניתן כקלט יסתיים עבור הקלט הנתון או לא.

 

תיאור מורחב בנושא בעיית העצירה ניתן למצוא בספר "אלגוריתמיקה" של דוד הראל עמ' 200.

ניתן להציג את בעיית העצירה בצורה מעניינת ע"י בעיית ה- Busy Beaver (הבונה התזזיתי).

 

הגדרת בעיית ה- Busy Beaver (BB)

נסתכל על מכונת טיורינג בעלת א"ב בינארי (רק שני תווים שונים: 1 והתו הריק שמקובל לסמן ב-D) המקבלת כקלט סרט אינסופי ריק. אם המכונה עוצרת, הפלט שלה יהיה מספר ה- 1 -ים המופיעים על הסרט כאשר היא עצרה. כעת נסתכל על אוסף כל המכונות הפועלות על א"ב בינארי ולהן n מצבים (לא כולל מצב העצירה). מתוך האוסף הזה, המכונה אשר מביאה לפלט של הכי הרבה מספרי 1 נקראת Busy Beaver עבור n. הפונקציה המחזירה את מספר ה-1 הגדול ביותר עבור מכונה עם n מצבים נקראת BB(n). אמנם לא ניתן למצוא אלגוריתם שעבור n כלשהו יחשב את BB(n), אבל מעניין לחפש מכונות טיורינג העוצרות עם פלט ארוך במיוחד.

הבעיה הוגדרה על ידי Tibor Rado  בשנת 1960 לערך.

עבור מספרים קטנים מאד של n ניתן למצוא את המכונה הטרודה ביותר, אבל עבור n³5, ערכו של BB(n) אינו ידוע. ניתן להתרשם מן הערכים בטבלה הבאה:

BB(n)

n

1

1

4

2

6

3

13

4

³ 4098

5

³ 95,524,079

6

 

עבור n=5 ידוע על מכונה המדפיסה 4098 אותיות לפני שהיא עוצרת.

עבור n=6 קיימת מכונה המדפיסה כמעט מאה מליון אותיות ועוצרת. קשה להאמין שמכונה כל כך קטנה יכולה להפיק פלט כל כך עצום ולעצור!!!

לדוגמא ניתן להסתכל על המכונה BB עבור n=3, אשר עוצרת אחרי 13 מעברים וכותבת 6 פעמים את התו 1 על הסרט:

 

הטבלה הבאה מתארת את פעולת המכונה מן המצב ההתחלתי ועד לעצירתה במצב H*:

 

מצב הסרט אחרי הפעולה

פעולה

אות

מצב

מספר

הסרט לפני פעולת המכונה

1, R,  q2

D

q1

1

1, L, q1

D

q2

2

1, L, q3

1

q1

3

1, L, q2

D

q3

4

1, L, q1

D

q2

5

1, R, q2

D

q1

6

1, R, q2

1

q2

7

1, R, q2

1

q2

8

1, R, q2

1

q2

9

1, R, q2

1

q2

10

1, L, q1

D

q2

11

1, L, q3

1

q1

12

1, R, H

1

q3

13

 

* הסבר מפורט של השורה הראשונה: המכונה נמצאת במצב q1 , על הסרט מופיע התו D, לכן על פי האיור של המכונה יש לכתוב את התו 1 במקום התו הנוכחי, לנוע ימינה (R) והמכונה עוברת למצב q2.

להלן המכונה BB עבור n=6 אשר עוצרת אחרי 8,690,333,381,690,951 מעברים (!!!) וכותבת 95,524,079 פעמים את התו 1 על הסרט:

 

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

 

הפעלה לכיתה

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

 

אלן טיורינג - Alan Mathison Turing

23 ביוני 1912 - 7 ביוני 1954

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

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

בשנת 1934 העלה טיורינג את הרעיון של "מכונת טיורינג", בניסיון לענות על שאלות העוסקות ביסודות המתמטיקה.

בשנים 1938-1936 למד באוניברסיטת פרינסטון שבארצות הברית, ובשנת 1938 השלים את עבודת הדוקטורט שלו (בהדרכת אלונזו צ'רץ' Alonzo Church ).

בשנת 1937 הצליח לפתור בדרך השלילה את הבעיה ה- 23 של הילברט (David Hilbert) ("האם קיים אלגוריתם שיכול לאמת או להפריך כל טענה לוגית במערכת לוגית שתהיה חזקה מספיק כדי לייצג את המספרים הטבעיים") ובמאמר בשם "על מספרים הניתנים לחישוב" הוא תיאר לראשונה את המכונה התיאורטית לפתרון שכונתה "מכונת טיורינג". טיורינג פיתח למעשה מודל תיאורטי של מחשב וסלל בכך את הדרך לתיאוריה המודרנית של מדעי המחשב.

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

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

במאמר שהתפרסם בשנת 1950 העלה את הרעיון של "מבחן טיורינג" במאמרו הנבואי "מכונות חישוב ואינטליגנציה". התיאוריה המתוארת במאמר היא שניתן לבנות מחשבים "חושבים" והציע אמת מידה - מבחן טיורינג - שתאפשר לקבוע האם המחשב אינטליגנטי. יחד עם חברו הטוב דויד צ'מפרנון הוא תכנן את תוכנית המחשב הראשונה שמשחקת שחמט "TuroChamp".

בשנת 1952 הורשע טיורינג בהומוסקסואליות, התנהגות שהייתה עבירה פלילית באנגליה של אותה עת. בגזר הדין ניתנה לו האפשרות לבחור בין עונש מאסר לבין טיפול הורמונלי, וטיורינג בחר באפשרות השנייה. הוא שקע בדיכאון וב-7 ביוני 1954 שם קץ לחייו בגיל 41.

 

פרס טיורינג

פרס טיורינג ע"ש אלן טיורינג מוענק ע"י ארגון ה-ACM, האגודה העולמית של מדעני המחשב, למדענים שתרמו תרומה מקורית, בעלת חשיבות יסודית וארוכת טווח לקידום מדעי המחשב. פרס טיורינג נחשב ל"פרס נובל" של עולם המחשבים. הפרס ניתן מדי שנה, החל משנת 1966. עד כה זכו בפרס שלושה מדעני מחשב ישראלים: בשנת 1976 מיכאל רבין מהאוניברסיטה העברית (יחד עם דנה סקוט), על מאמרם העוסק באוטומטים סופיים, שהציג את הרעיון של מכונות לא דטרמיניסטיות; בשנת 1996 אמיר פנואלי ממכון ויצמן למדע, על עבודתו המקורית להבאת לוגיקה טמפוראלית למדעי המחשב ועל תרומתו לאימות תוכנה; שנת 2002 עדי שמיר ממכון ויצמן למדע (יחד עם רונלד ריבסט ולאונרד אדלמן) על תרומתם לפיתוח הצפנה במפתח ציבורי.

 

מקורות

אלן טיורינג: אתר הבית ופורטל מצוין

פרס טיורינג

הבעייה BB וקישורים נוספים

צוות שמנהל מחקר בתחום BB

מחקר עכשווי בנושא BB

Glass, M. (1997). Blank Tape Halting

 Problem vs. the Busy Beaver Function

מודל Turmite של מכונת טיורינג דו-מימדית

מודלים שונים של מכונות טיורינג

חייו של טיורינג ותרומתו למדעי המחשב

http://cse.proj.ac.il/hebetim/5/turing.htm

המחזה של משפט טיורינג

http://cse.proj.ac.il/hebetim/2/turing.htm

 

חזרה לעמוד הראשי