הבעיה העשירית של הילברט - מבוא

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

אני הולך להתבסס כאן בעיקר על האופן שבו הפרטים מוצגים במאמר הפנטסטי של מרטין דיוויס, Hilbert’s Tenth Problem is Unsolvable, אבל קרוב לודאי שאחפף ואולי אציג דברים בצורה שונה.

נתחיל בהתחלה, עם הילברט. את הילברט הזכרתי כל כך הרבה פעמים בבלוג שנראה לי מוזר להציג אותו מחדש; הוא היה אחד מגדולי המתמטיקאים של כל הזמן, ובשנת 1900 היה הסופרסטאר הבלתי מעורער של עולם המתמטיקה; מתמטיקאי מגוון מאוד שאומרים עליו ששלט בכל תחומי המתמטיקה של זמנו. לכן, כשהוא נשא נאום בקונגרס מתמטי שנערך בפריז בשנת 1900 ובו הציג רשימה של 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.

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

\( x+y=2 \)

זו משוואה עם שלל פתרונות, למשל \( x=y=1 \). עוד פתרון הוא \( x=\frac{1}{2},y=\frac{3}{2} \) ועוד פתרון הוא \( x=\pi,y=2-\pi \), אבל כשאנחנו מדברים על משוואות דיופנטיות אנחנו מתעניינים רק בפתרונות שהם מספרים שלמים, כלומר הפתרון הראשון לגיטימי, ושני האחרים לא. כך למשל למשוואה \( x^{2}=2 \) אין פתרון כלל, למרות ש-\( x=\sqrt{2} \) מקיים את השוויון, וזה בגלל ש-\( \sqrt{2} \) הוא לא מספר שלם (למי שתוהה למה הילברט אומר Rational Integers - זה כדי להבדיל אותם משלמים אלגבריים שהם הכללה של מספרים שלמים “רגילים” שצצה בתורת המספרים האלגברית, וזה לא רלוונטי לכל הדיון שלנו).

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

ובכן, הבה ונתבונן במשוואה הבאה:

\( x^{3}+y^{3}=z^{3} \)

למשוואה הזו יש כמה פתרונות ברורים - אלו שבהם \( x \) או \( y \) הם אפס, אבל בואו נתעלם מזה לשניה ונשאל את עצמנו אם יש לה עוד פתרונות בשלמים (לצורך העניין אפשר לדרוש שכל המשתנים יקבלו ערכים חיוביים ממש). התשובה היא לא; זה מקרה פרטי של המשפט האחרון של פרמה. לא יותר מדי קשה להוכיח שהתשובה היא לא, אבל זה דורש עבודה. ואז מגיעים למשוואה \( x^{5}+y^{5}=z^{5} \) שדורשת עוד יותר עבודה; וכן הלאה וכן הלאה, ומשוואה כמו \( x^{37}+y^{37}=z^{37} \) תדרוש המון עבודה, ובכל המקרים הללו סתם עבודה שחורה לא מספיקה - צריך יצירתיות וכושר דמיון כדי להתגבר על הבעיה. והמשוואות הללו הן מקרה פרטי פשוט של הבעיה הכללית שהילברט דיבר עליה… (שוב, אם מתעלמים מהפתרון הטריוויאלי של האפסים).

אוקיי, אז הבנו שהבעיה כנראה לא קלה. בואו נבין לרגע עד הסוף מה זו “משוואה פולינומית”. יש לנו מספר כלשהו של משתנים, שאנחנו מסמנים בתור \( x,y,z \) וכדומה (או בתור \( x_{1},x_{2},\dots,x_{n} \) אם יש יותר מדי). מותר לנו לחבר אותם, לחסר אותם ולהכפיל אותם זה בזה ובעצמם, ואת כל זה אנחנו משווים בסוף לאפס. זה הכל. כך למשל \( x^2y^2-15=0 \) היא משוואה דיופנטית (חסרת פתרון) ו-\( x^2y^2-16=0 \) היא משוואה דיופנטית (עם הפתרון \( x=y=2 \)), וגם \( x^{5}y+17y^{3}z^{4}=16xyzw \) היא משוואה דיופנטית (היא לא מושווה לאפס, אבל אפשר להעביר את ה-\( 16xyzw \) אגף). באופן פורמלי, אם \( p\left(x_{1},\dots,x_{n}\right) \) הוא פולינום כלשהו במשתנים \( x_{1},\dots,x_{n} \), אז הוא מגדיר את המשוואה הדיופנטית \( p\left(x_{1},\dots,x_{n}\right)=0 \).

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

\( x+y=8 \)

\( y+z=16 \)

שיש לה אינסוף פתרונות (למשל, \( x=8,y=0,z=16 \))? התשובה היא שאפשר, כי אפשר להמיר כל מערכת של מספר סופי של משוואות למשוואה יחידה. בואו נניח שיש לנו מערכת שהמשוואות בה מוגדרות על ידי הפולינומים \( p_{1},\dots,p_{k} \) (אני לא כותב את המשתנים שלהם כדי לא לסרבל). אז הנה לכם משוואה אחת שיש לה פתרון אם ורק אם קיימת השמה לכל המשתנים שמאפסת בו זמנית את כל המשוואות:

\( p_{1}^{2}+p_{2}^{2}+\dots+p_{k}^{2}=0 \)

מה קורה כאן? יש לנו סכום של ריבועים. ריבועים של מספרים שלמים (והשמה של מספרים שלמים ב-\( p \)-ים יכולה להחזיר רק מספרים שלמים) הם תמיד מספרים אי-שליליים; אם \( p_{i}\left(x_{1},\dots,x_{n}\right)\ne0 \) אז \( p_{i}^{2}\left(x_{1},\dots,x_{n}\right)>0 \), ולכן מספיק שאחת מהמשוואות לא תתאפס כדי שהביטוי \( p_{1}^{2}+p_{2}^{2}+\dots+p_{k}^{2} \) כולו יהיה גדול מאפס. לכן מבחינתנו אין הבדל בין לפתור מערכת של משוואות דיופנטיות ובין לפתור אחת כזו, ונבחר את הניסוח שיותר נוח לנו כאשר נזדקק לו. אם לחדד - הוכחה שקיים אלגוריתם שפותר כל מערכת משוואות דיופנטית בוודאי תוכיח שקיים אלגוריתם שפותר כל משוואה כזו (כי משוואה היא מקרה פרטי של מערכת משוואות), אבל גם הוכחה שקיים אלגוריתם שפותר משוואה בודדת מראה שקיים אלגוריתם שפותר מערכת משוואות.

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

מה התעלול? נניח ש-\( p\left(x_{1},\dots,x_{n}\right) \) היא משוואה שאנחנו רוצים לבדוק אם יש לה פתרון בשלמים חיוביים. אז נמיר אותה למשוואה המוזרה הבאה:

\( p\left(1+a_{1}^{2}+b_{1}^{2}+c_{1}^{2}+d_{1}^{2},\dots,1+a_{n}^{2}+b_{n}^{2}+c_{n}^{2}+d_{n}^{2}\right) \)

ונבדוק אם יש לה פתרון בשלמים בכלל.

מה קרה כאן? החלפנו כל משתנה \( x_{i} \) בביטוי \( 1+a_{i}^{2}+b_{i}^{2}+c_{i}^{2}+d_{i}^{2} \) כאשר כל האותיות הללו הן משתנים. בבירור, מהנימוק שכבר נתתי כאן, כל הצבה אפשרית של ערכים במשתנים הללו תחזיר מספר חיובי ממש (1 ועוד מספר שהוא גדול או שווה לאפס). מצד שני, כל מספר טבעי חיובי יכול להתקבל כך; זו תוצאה לא טריוויאלית שנקראת “משפט ארבעת הריבועים של לגראנז’” ואני מקווה להוכיח יום אחד בבלוג (ההוכחה אינה קשה יותר מדי, והיא מהווה תירוץ טוב לדבר על קווטרניונים). אני חושב שהתעלול הזה מקסים למדי.

כעת, הבה ונעבור לסקירה קצרה ממעוף הציפור של מה שעלה בגורל הבעיה הזו.

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

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

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

Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses, or in the sense contemplated. Such proofs of impossibility were effected by the ancients, for instance when they showed that the ratio of the hypotenuse to the side of an isosceles right triangle is irrational. In later mathematics, the question as to the impossibility of certain solutions plays a preeminent part, and we perceive in this way that old and difficult problems, such as the proof of the axiom of parallels, the squaring of the circle, or the solution of equations of the fifth degree by radicals have finally found fully satisfactory and rigorous solutions, although in another sense than that originally intended. It is probably this important fact along with other philosophical reasons that gives rise to the conviction (which every mathematician shares, but which no one has as yet supported by a proof) that every definite mathematical problem must necessarily be susceptible of an exact settlement, either in the form of an actual answer to the question asked, or by the proof of the impossibility of its solution and therewith the necessary failure of all attempts.

אני חושב שהילברט היה מרוצה מגורל הבעיה שלו.

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

הרעיון הראשון של דיוויס (ובאופן בלתי תלוי בו, רובינסון) היה לעבור לדבר על קבוצות דיופנטיות. בהינתן פולינום \( p\left(x_{1},\dots,x_{n},y_{1},\dots,y_{m}\right) \) שחילקנו את משתניו לשתי קבוצות, ה-\( x \)-ים וה-\( y \)-ים, אפשר להציב ערכים בתוך ה-\( x \)-ים כדי לקבל פולינום חדש, \( q\left(y_{1},\dots,y_{m}\right)=p\left(a_{1},\dots,a_{n},y_{1},\dots,y_{m}\right) \). עכשיו נשאל את השאלה - האם למשוואה הדיופנטית \( q\left(y_{1},\dots,y_{m}\right)=0 \) יש פתרון, או לא?

הקבוצה הדיופנטית ש-\( p \) מגדיר היא הקבוצה של כל הערכים \( \left(a_{1},\dots,a_{n}\right) \) שאפשר להציב ב-\( x \)-ים ולקבל משוואה דיופנטית פתירה. בכתיבה מתמטית פורמלית:

\( S_{p}=\left\{ \left(a_{1},\dots,a_{n}\right)\ |\ \exists\left(b_{1},\dots,b_{m}\right)p\left(a_{1},\dots,a_{n},b_{1},\dots,b_{m}\right)=0\right\} \)

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

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

\( p\left(x,y_{1},y_{2}\right)=x-\left(1+y_{1}\right)\left(1+y_{2}\right) \). נניח שהצבנו \( x=8 \), אז נקבל את הפולינום \( p\left(8,y_{1},y_{2}\right)=8-\left(1+y_{1}\right)\left(1+y_{2}\right) \). המשוואה הדיופנטית הזו פתירה על ידי ההשמה \( y_{1}=1,y_{2}=3 \) ולכן \( 8\in S_{p} \) במקרה הזה. לעומת זאת, אם נציב \( x=7 \) נקבל משוואה דיופנטית לא פתירה ולכן \( 7\notin S_{p} \) (תרגיל - למה \( \left(1+y_{1}\right)\left(1+y_{2}\right) \) ולא סתם \( y_{1}y_{2} \)?)

במילים אחרות, אפשר להגדיר את קבוצת המספרים הפריקים באמצעות הפולינום \( p \). זה מצביע על הבעיה הכללית שתעניין אותנו - נתונה קבוצה של מספרים (או של זוגות/שלשות וכדומה של מספרים); האם קיים פולינום \( p \) כך שהקבוצה שלנו שווה ל-\( S_{p} \)? או במילים אחרות, האם הקבוצה הנתונה היא דיופנטית?

עוד דוגמה - יחס החלוקה. פורמלית, \( a \) מחלק את \( b \) אם קיים \( t \) כך ש-\( at=b \), ומסמנים זאת \( a|b \). הפולינום \( p\left(x_{1},x_{2},y\right)=x_{2}-x_{1}y \) מגדיר את הקבוצה \( \left\{ \left(x_{1},x_{2}\right)\ |\ x_{1}|x_{2}\right\} \), ולכן אנחנו אומרים שהוא מגדיר את יחס החלוקה (פורמלית, כך בדיוק יחס החלוקה מוגדר - קבוצת הזוגות אשר מקיימים את היחס).

נניח שהבנו את העקרון - מה עכשיו? ובכן, עכשיו נכנסת לתמונה תורת החישוביות. בתורת החישוביות גם כן מתעניינים בקבוצות של מספרים טבעיים; אמנם, בדרך כלל האובייקט שמדברים עליו הוא שפות, אבל אפשר באותה מידה לדבר גם על קבוצות של טבעיים בלי להגביל את כלליות הדיון. בהינתן קבוצה \( S \) של טבעיים, המטרה של תורת החישוביות היא לבדוק אם קיים אלגוריתם שמכריע, בהינתן מספר טבעי \( a \), האם \( a\in S \) או לא; ובדומה גם עבור קבוצות של \( n \)-יות של טבעיים (\( n \)-יה היא הכללה של זוג ושלשה - \( \left(a_{1},\dots,a_{n}\right) \)). אם יש אלגוריתם כזה אומרים ש-\( S \) היא כריעה (או, מסיבה שתובהר בפוסטים הבאים, רקורסיבית).

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

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

כעת, ההוכחה שהבעיה העשירית של הילברט אינה כריעה ניתנת לתיאור כמורכבת משלוש טענות שמתחברות להן יחדיו:

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

את טענה 1 כבר תיארתי. טענה 2 ברורה למדי - נניח ש-\( S_{p} \) היא קבוצה דיופנטית ואנחנו רוצים לבדוק האם \( \left(a_{1},\dots,a_{n}\right) \) שייך אליה. אז נציב את הערכים הללו ב-\( p \), נקבל משוואה דיופנטית, וכעת נפעיל את האלגוריתם הדמיוני של הילברט ונבדוק האם המשוואה הדיופנטית פתירה או לא. אם היא פתירה, נאמר ש-\( \left(a_{1},\dots,a_{n}\right)\in S \) ואחרת נאמר ש-\( \left(a_{1},\dots,a_{n}\right)\notin S \). פשוט למדי, לא?

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

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

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