ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
בעית העצירה 
 
 פה דווקא לא מסובך לקבוע: יש עצירה    צילום: TheAlieness GiselaGiardino / פליקר    
לפרק את הבייט |
 

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

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

מה הבעיה?

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

הסתכלו על הכאילו-תוכנה הבאה, שנקראת "תקוע_542":

1. קבל מספר מהמשתמש
2. אם המספר שהתקבל שווה ל-542, אז לך לשורה 3, אחרת לך לשורה 4
3. חזור לשורה 2
4. סוף.

בהינתן הקלטים 3, 1000 ו-542, האם התוכנה הזו מגיעה לסוף (שורה 4) או לא? שאלה קלה, נכון? הקלט 542 יגרום ללולאה אינסופית של השורות 2 ו-3, והתוכנה לעולם לא תעצור. עבור כל מספר אחר, לעומת זאת, היא תעצור מייד. נעבור לשאלה אחרת, קצת יותר קשה: האם אפשר לכתוב תוכנה נוספת, שתקבל כקלט את התוכנה "תקוע_542" ומספר ותקבע, כפי שאתם קבעתם, אם "תקוע_542" עוצרת או לא בהינתן המספר הזה?

או באופן כללי יותר, האם אפשר לכתוב תוכנה בשם "האם_עוצרת" שתקבל כקלט תוכנה P כלשהי ונתון I כלשהו ותבדוק אם P עוצרת בהינתן I כקלט?

שימו לב למגבלה חשובה אחת: התוכנה "האם_עוצרת" חייבת לתת תשובה בזמן סופי. יכולות להיות תוכנות שעוצרות אחרי מיליארד שנה, או לא עוצרות בכלל, אבל לנו אין את הלוקסוס להריץ אותן בסימולציה ולחכות. את ההתנהגות של "תקוע_542" הבנו באופן מיידי בלי להריץ אותה בפועל, ואנחנו מחפשים תוכנה שתוכל לעשות את אותו הדבר. גם אם ייקח לה שנה, לא נורא – העיקר שזה יבוצע בזמן סופי.
 
דאגלס הופשטטר
 דאגלס הופשטטר    צילום: וויקיפדיה 
 
 
מדען המחשבים והפילוסוף דגלאס הופשטטר, בספרו המפורסם והמקסים "Godel, Escher, Bach", מציין בעיה אינטואיטיבית ברעיון של תוכנה שכזו. לצורך העניין, נניח שכבר הצלחנו לכתוב אותה. כעת, בואו נכתוב עוד תוכנה פשוטה, שעוברת על כל המספרים הזוגיים מ-4 ועד אינסוף (עזבו לרגע את מגבלות הזיכרון של המחשב הפיזי), ובודקת עבור כל אחד מהם אם ניתן לבטא אותו כסכום של שני ראשוניים. נקרא לה "בדיקת_גולדבך" ונכתוב אותה כך שברגע שהיא מגלה יוצא-דופן, היא עוצרת. אם נזין את "בדיקת_גולדבך" לתוך "האם_עוצרת", נדע בתוך זמן סופי אם השערת גולדבך נכונה או לא! כמובן, גם אם יסתבר שהיא נכונה, זו לא תהיה הוכחה מתמטית במובן המקובל של המילה – ובכל זאת, יהיה מדובר בהישג מדהים.

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

תשובה שלילית, הוכחה על דרך השלילה

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

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

האם_עוצרת(תקוע_542, 1000) => כן
האם_עוצרת(תקוע_542, 542) => לא

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

1. אם האם_עוצרת(P, P) = כן, אז החזר "כן", אחרת החזר "לא"
2. סוף.

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

1. אם האם_עוצרת_על_עצמה(P) = כן, אז לך לשורה 2, אחרת לך לשורה 4
2. לך לשורה 3
3. חזור לשורה 2
4. סוף.

כלומר, "תנאי_אכזרי" בודקת אם P עוצרת בהינתן P. אם כן, היא מכניסה את עצמה ללולאה אינסופית, ואם לא – היא עוצרת. כל אדם הגיוני ישאל את עצמו מי לעזאזל צריך את "תנאי_אכזרי". למה היא טובה? מה היא מוסיפה לנו לחיים? אלה שאלות טובות, אבל לא רלוונטיות. הדבר היחיד שרלוונטי כרגע הוא ש"תנאי_אכזרי" היא תוכנה חוקית למהדרין. אין בה שום פגם תיאורטי או מעשי, וכל קומפיילר יכול להדר ולהריץ אותה.

והנה, סוף כל סוף, הקטע האכזרי באמת. מה יקרה אם נריץ

תנאי_אכזרי(תנאי_אכזרי)

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

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

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

עוד קצת פסימיות

המתמטיקאי רוג'ר פנרוז לקח את הטענה הזו צעד אחד קדימה והשליך אותה על נפש האדם. ישנם רבים כיום שמאמינים שהנפש איננה ממשות בפני עצמה אלא בסך הכל תוצר של תהליכים חשמליים וכימיים במוח, שמתנהגים לפי חוקי טבע קבועים וברורים. אם זה נכון, אומר פנרוז, הרי שאפשר (בתיאוריה, כמובן) להכניס למחשב את כל הפרמטרים של המוח החומרי ואת כל חוקי הטבע הרלוונטיים, וליצור מכל זה אלגוריתם ממוחשב שיתנהג, יחשוב וירגיש בדיוק כמו מוח אנושי. אבל אלגוריתם, כפי שהוכחנו לפני רגע, אינו יכול לפתור את בעיית העצירה. מצד שני, קשה לנו להאמין שהמוח שלנו מוגבל בצורה כזאת – האם האדם, שפיתח בעצמו את כל התיאוריה של המחשבים, לא יהיה מסוגל להסתכל על תוכנית מחשב כלשהי ולהחליט אם היא עוצרת או לא? האם יש גבול ברור כל-כך ליכולות השכליות של האדם? פנרוז טוען שלא, ומסיק מכך שלא ייתכן שהנפש היא תוצר של המוח החומרי. דיון מלא בבעיה ובהשלכותיה הוא הרבה מעבר להיקף של טור זה, ולכן ניאלץ לעצור כאן.
 
נ.ב. המחשת בעיית העצירה בטור זה התבססה (בחופשיות) על תוכן מאת קרייג קפלן, פרופסור למדעי המחשב מאוניברסיטת ווטרלו שבאונטריו, קנדה, באישורו.
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by