על משוואות דיופנטיות ושאר בעיות שהשוליים הללו צרים מלהכיל

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

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

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

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

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

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

\( x^n+y^n=z^n \)

כאן \( n \) הוא מספר שנתון מראש (כלומר, אין משוואה בודדת; יש לנו אוסף של משוואות שונות), ואילו \( x,y,z \) הם משתנים. אם היינו מרשים למשתנים לקבל ערכים של מספרים מרוכבים, תמיד היה פתרון לכל משוואה (בשל המשפט היסודי של האלגברה). מכיוון שאנו מרשים רק פתרונות שלמים, המשחק מסתבך. עבור \( n=2 \) לא חסרים פתרונות: הפתרון הפשוט ביותר הוא \( x=3,y=4,z=5 \) ואכן \( 3^2+4^2=5^2 \). כל פתרון של המשוואה במקרה הזה נקרא “שלשה פיתגורית”, על שם משפט פיתגורס (שאומר שבמשולש ישר זווית, ריבוע אורך אחת השוקיים - נכנה אותו \( x \), ועוד ריבוע אורך השוק השנייה - נכנה אותו \( y \), שווה לריבוע אורך היתר - הצלע שמול הזווית בת תשעים המעלות - שאותו נכנה \( z \)). יש נוסחה נאה לייצור שלשות פיתגוריות ככל שרק נרצה, והתחום הזה חקור וידוע היטב (וגם מהווה בסיס למחלוקת בכל הנוגע למתמטיקה הבבלית - האם הם ידעו את הנוסחה או לא? גם על כך אני מקווה לכתוב בפוסט נפרד).

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

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

מה שהילברט כן רצה - הבעיה העשירית שלו - הוא, ואני מצטט את התרגום לאנגלית:

"Given a diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: to devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers."

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

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

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