המחשב הגדול מן החלומות

האם עתיד להופיע בעולמנו מחשב-משיח, ואלו בעיות הוא יעזור לפתור?

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

“פוק החל לאבד את סבלנותו. הוא הדף את מחברתו מלפניו ומילמל 'כל העסק נעשה משיחי מדי, לטעמי'.

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

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

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

בראשן של אלה עומדות בעיות NPC – non-deterministically polynomial complete) שהן המורכבות בבעיות NP. אם יימצא האלגוריתם שיאפשר את פתרונה של אחת מאלה בזמן פולינומיאלי, יוסר המכשול ויהיה אפשר לפתור את כל בעיות ה-NP בזמן מתקבל על הדעת שכזה. לדיון בבעיות אלה יש גם לא מעט השלכות מעשיות: החל בפישוט הצפנת קודים ופיצוחם וכלה בתרומה לניסיונות לחסוך בבד בייצור ריפוד למושבי מטוסים.

שיחה דומה מאוד לזו שניהלו פוק ו”הרהור עמוק” מתנהלת זה שנים במסדרונות המחלקות למתמטיקה ולמדע המחשב באוניברסיטאות ובמשרדי חברות השואפות לפתח חומרת מחשב עתידית. זאת, בניסיון למצוא פתרון לאחת הבעיות המתמטיות המטרידות של כל הזמנים: סוגיית הסבירות; כיצד יוכלו מחשבים עתידיים לפתור בעיות NPC בזמן פולינומיאלי – או, בשפת האלגברה, לפתור את השאלה האם P=NP?

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

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

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

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

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

אם יתגשם חזונו של ביל גייטס וכל אדם על פני כדור הארץ יהיה בעליו של מחשב פנטיום 4 המצויד בתוכנת “חלונות”, ואם יעמלו כל תושבי העולם על הרשימות ולא יעשו דבר מלבד זה – גם אז יהיה אפשר לבדוק כ-10 בחזקת 25 רשימות בשנה. כלומר, יהיה אז צורך להמתין 10 בחזקת 71 שנים (או מיליארד מיליארדים של מיליארדי מיליארד מיליארדים של מיליארדי מיליארד מיליארדים של שנים) עד שתושלם העבודה.

מובן אפוא מדוע מסיק מכון קליי כי שום ציוויליזציה עתידית לא תייצר מחשב-על שיפתור את הבעיה באמצעות “כוח ישיר, כלומר, סקירת כל הצירופים האפשריים של מאה תלמידים”. אך אנשי המכון ממהרים להוסיף: “אולי האשם הוא בחוסר דמיונם של המתכנתים”. כלומר, אולי אפשר בכל זאת לפתור את חידת ה-P=NP בעזרת המחשבים הקיימים אלא שאיש פשוט עוד לא עלה על הדרך הזאת. המכון מציע ברשת האינטרנט פרס של מיליון דולר לכל מי שיפתור את הבעיה.

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

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

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

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