הבעיה העשירית של הילברט

ה"בעיה העשירית" של הילברט שואלת האם יש אלגוריתם כללי שמחליט, עבור משוואה פולינומית עם מקדמים שלמים, האם קיימים לה פתרונות במספרים שלמים. אפשר לתת דוגמאות קשות יחסית כמו המשוואה x^2-61y^2=1 או משוואה מורכבת יותר עם חזקות וריבועים. הילברט הציג את הבעיה ב-1900, ובאותו זמן הרעיון שאפשר להוכיח שאף אלגוריתם כזה אינו קיים נחשב בלתי נתפס. רק אחרי עבודות לוגיקה במאה ה-20, כולל של גדל, הדבר התחיל להיראות אפשרי.

(הילברט הציג את הבעיה עבור שלמים, אך בעזרת משפט ארבעת הריבועים של לגראנז' אפשר לעבור לטבעיים.)

במחצית השנייה של המאה ה-20 נבנה הקשר בין הבעיה לעקרונות חישוביות. צ'רץ', טיורינג ופוסט הראו שיש קבצים של מספרים שהם ניתנים למנייה חישובית, כלומר יש אלגוריתם שמייצר את כל האיברים שלהם אחד אחרי השני, אך אינם חישוביים, כלומר אין אלגוריתם שמחליט לכל מספר האם הוא שייך לקבוצה או לא. דייוויס הציג את המושג "הצגה דיופנטית": קבוצה ניתנת להצגה כך אם יש פולינום P שכל ערך a ששייך לקבוצה הוא הרכיב הראשון של פתרון למשוואה P(a,x1,...,xn)=0. דייוויס הראה שכל קבוצה עם הצגה דיופנטית ניתנת למנייה חישובית, והעלה את ההשערה ההפוכה: שכל קבוצה ניתנת למנייה חישובית גם ניתנת להצגה דיופנטית.

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

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

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

המכה הסופית הגיעה בעבודתו של יורי מאטיאשביץ'. בסוף שנות ה-60 וראשית ה-70 הוא הראה שיחסים מעריכיים מסוימים, ובפרט קשרים הקשורים לסדרת פיבונאצ'י (שגדלה בקצב מעריכי), ניתנים להצגה דיופנטית פולינומית. התוצאות האלה השלימו את שרשרת ההוכחות והובילו למסקנה המכרעת: לא קיים אלגוריתם כללי שמכריע האם משוואה דיופנטית במקדמים שלמים יש לה פתרון בשלמים. במקור מצוין כי התשובה הוכרה כשילילית סביב 1970, וההצגה המפורטת באמצעות פיבונאצ'י הושלמה על ידי מאטיאשביץ' בתחילת שנות ה-70.

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

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

הילברט הציג את השאלה ב-1900. הרבה שנים חשבו שאולי יש חוק כזה. אחרי זמן רב הוכיחו שזה בלתי אפשרי.

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

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

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

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

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