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

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

למי שרוצה את כל הפרטים, נמליץ על הסרטון הבא [3].

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

התשובה לכך היא התזה (החלשה) של צ'רצ'-טיורינג [4], על שם אלן טיורינג וחלוץ נוסף של מדעי המחשב בשם אלונזו צ'רצ' [5]. התזה גורסת שכל דבר שניתן לחשב בצורה כלשהי, ניתן לחשב גם באמצעות מכונת טיורינג. התזה הזו היא הבסיס שעליו נבנו כמעט כל מדעי המחשב התיאורטיים. חשוב להבין שהתזה של צ'רצ'-טיורינג אינה טענה מתמטית, אלא פיזיקלית. היא טוענת טענה על היקום, ועל סוג המכונות שאפשרי לבנות בו. לכן אין שום דרך להוכיח אותה. זו אמירה מאוד מרחיקת לכת, אבל היא עומדת במבחן המציאות כבר קרוב למאה שנים. כל המחשבים שאנחנו מכירים, בפרקטיקה ובתאוריה, שקולים למכונת טיורינג. יש המשערים שניתן יהיה לבנות מחשב יותר חזק עם הנחות פיזיקליות מאוד מרחיקות לכת, כמו גישה לחורים שחורים או לולאות זמן-חלל סגורות [6], אבל אפילו המודלים האלו, שממנפים את תופעות הטבע הקיצוניות ביותר שהבנת היקום של המין האנושי מסוגלת לספק, מאוד שנויים במחלוקת.

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

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

בעיית העצירה מהווה דוגמה ראשונה למה שנקרא בעיה בלתי-כריעה (undecidable, מלשון הכרעה) [8], והיא רחוקה מלהיות הדוגמה היחידה. מאז ימי טיורינג נמצאו אינספור בעיות לא כריעות [9]. חלקן הונדסו כדי להיות אי-כריעות, וחלקן נבעו באופן טבעי מתחומי מתמטיקה רבים. אבל אי כריעות לא הטרידה פיזיקאים במיוחד. מדעי הטבע הביאו איתם הרבה בעיות קשות מאוד, אבל כולן היו בעיות שנראה שעם מספיק כוח חישובי אפשר, עקרונית, לפתור. זאת עד שבשנת 2015 פורסם במגזין נייצ'ר מאמר עצום באורך כ-150 עמודים של מדען המחשב טובי קיוביט (כן, זה השם שלו) ושותפים, אשר מוכיח שבעיה פיזיקלית די כללית בשם "בעיית הפער הספקטרלי" היא בלתי כריעה [10]. עצם העובדה שמאמר בנושא כל כך תיאורטי פורסם במגזין המרכזי של מדעי הטבע ראויה לציון בפני עצמה.

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

קישורים והרחבות:

[1] אלן טיורינג

[2] מכונת טיורינג

[3] סרטון שמסביר על מכונת טיורינג

[4] התזה החלשה של צ'רצ'-טיורינג

[5] אלונזו צ'רצ'

[6] על-מחשוב

[7] הוכחת אי-כריעות בעיית העצירה, בבלוג - "לא מדוייק"

[8] בעיות הכרעה

[9] רשימת בעיות לא כריעות

[10] אי-כריעות של בעיית הפער הספקטרלי