הקיים הנעלם - הדוגמה הרמאית

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

מספר ראשוני הוא מספר שמחלקיו הם הוא עצמו ו-1 בלבד (למשל, 13). השערת גולדבך היא ההשערה שכל מספר זוגי הגדול מ-2 ניתן לכתיבה כסכום של שני מספרים ראשוניים. למשל, את 16 אפשר לכתוב בתור 13 ועוד 3. את 24 אפשר לכתוב בתור 19 ועוד 5, וכן הלאה וכן הלאה.

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

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

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

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

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

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

1. הוצא את הפלט "השערת גולדבך נכונה".

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

1. הוצא את הפלט "השערת גולדבך אינה נכונה".

ובכן, אם השערת גולדבך אינה נכונה, זה האלגוריתם המכריע שרצינו.

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

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

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

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

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

אבל כן, זה עדיין מרגיש כמו רמאות אחת גדולה.