הצגת המקור של הדף "הבעיה העשירית של הילברט"

'''הבעיה העשירית''' היא אחת מ[[23 הבעיות של הילברט|עשרים ושלוש הבעיות]] שהציג [[דויד הילברט]] בקונגרס המתמטי של שנת [[1900]]. בעיה זו היא מהבעיות המפורסמות ביותר ב[[מתמטיקה]] של [[המאה ה-20]], ותולדותיה הן אבני דרך בולטות בהתפתחות ה[[לוגיקה מתמטית|לוגיקה המתמטית]] ו[[מדעי המחשב]] התאורטיים. הדרישה שהציגה הבעיה:
:{{ציטוטון|למצוא [[אלגוריתם]] שיקבע האם ל[[משוואה דיופנטית]] [[פולינום|פולינומית]] נתונה יש פתרון ב[[מספר טבעי|מספרים טבעיים]].}}

(הילברט הציג את הבעיה שלו עבור [[מספר שלם|מספרים שלמים]]. אולם אפשר לראות ששתי הבעיות שקולות זו לזו בעזרת [[משפט ארבעת הריבועים של לגראנז']] על הצגת מספר טבעי כסכום של ארבעה ריבועים).

האלגוריתם, אם קיים כזה, אמור לקבל משוואה, כדוגמת <math>\ x^2-61y^2=1</math> או <math>\ 4(x^6-x^4y^3+z^2)^2+(x^3-yz^3)^2-1=0</math>, ולקבוע בתוך זמן סופי האם קיים לה פתרון במספרים שלמים. 

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

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

==הצעד הראשון: הקשר לחישוביות==

ב-[[1950]] כתב [[מרטין דייוויס]] את תזת ה[[דוקטורט]] שלו בהנחייתו של [[אלונזו צ'רץ']], ובה עסק ברעיון של "הצגה דיופנטית" של [[קבוצה (מתמטיקה)|קבוצה]], והעלה את הרעיון שהוביל בסופו של דבר לפתרון הבעיה העשירית של הילברט. הקבוצות שאנו עוסקים בהן כאן הן כולן קבוצות של מספרים טבעיים. 
* [[קבוצה רקורסיבית|קבוצה חישובית]] היא קבוצה שקיים אלגוריתם המכריע לגבי השייכות אליה. כלומר: יש אלגוריתם S שהקלט שלו הוא מספר טבעי, והוא מחזיר - בזמן סופי - את התשובה "כן" או "לא" לגבי ההשתייכות לקבוצה.
* מושג חלש יותר הוא זה של [[קבוצה ניתנת למנייה רקורסיבית|קבוצה הניתנת למנייה חישובית]]: לקבוצה כזו יש אלגוריתם שיכול '''לזהות''' איברים שלה, אבל אין דורשים ממנו תשובה שלילית אם האיבר אינו שייך לקבוצה. האלגוריתם חייב לענות בזמן סופי אם הקלט שייך לקבוצה, אבל עבור קלט שאינו שייך לקבוצה הוא עשוי לרוץ לנצח. מובן שכל קבוצה חישובית היא בפרט ניתנת למנייה חישובית.
* הגדרה אחרת של אותו מושג: 'קבוצה הניתנת למנייה חישובית' היא קבוצה שקיים אלגוריתם שיכול להציג כל אחד מאיבריה בזמן סופי. אין מקום לדרוש שהאלגוריתם יציג בזמן סופי את כל הקבוצה - שהרי זו עשויה להיות [[קבוצה אינסופית]]. במקום זה, האלגוריתם צריך לעבור ממספר למספר בקבוצה, כאשר כל צעד נמשך זמן סופי, וב(אינ)סופו של דבר מכסה את הקבוצה כולה. 

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

דייוויס הציע להתבונן בקבוצות שניתנות ל"הצגה דיופנטית". קבוצה כזו היא קבוצת כל המספרים הטבעיים a שעבורם קיים פתרון למשוואה הדיופנטית הפולינומית <math>\ P(a,x_1,x_2,...,x_n)=0</math>. כל פולינום P במקדמים שלמים קובע הצגה דיופנטית של קבוצה: הקבוצה מורכבת מן הרכיב הראשון בכל פתרון <math>\ (a,x_1,...,x_n)</math> של הפולינום P. 

ההבחנה החשובה של דייוויס היא שכל קבוצה בעלת הצגה דיופנטית בהכרח גם ניתנת למנייה חישובית (ההוכחה מבוססת על העובדה שהקבוצה <math>\ \mathbb{N}^{n+1}</math> [[קבוצה בת מנייה|בת מנייה]]). דייוויס העלה את ההשערה שגם הכיוון ההפוך נכון: שלכל קבוצה הניתנת למנייה חישובית, אפשר למצוא הצגה דיופנטית. 

נשארה עוד פיסה אחת להשלמת התמונה: האלגוריתם של הילברט, אם קיים כזה, מראה שקבוצה B בעלת הצגה דיופנטית היא תמיד חישובית. אם הקבוצה מוצגת על ידי המשוואה P, האלגוריתם ההיפותטי של הילברט יכול להתבונן במשוואה <math>\ P(b,x_1,...,x_n)=0</math>, ולהכריע - לכל ערך נתון של b - האם יש לה פתרון במשתנים <math>\ x_1,...,x_n</math>. בכך האלגוריתם מכריע האם b שייך לקבוצה B או לא, ומכאן ש- B חישובית.

==סיכום ביניים==

[[תמונה:Hilbert 10th problem - 1.jpg|שמאל|ממוזער|280px|קיומו של האלגוריתם של הילברט סותר את השערתו של דייוויס, מכיוון שיש קבוצות ניתנות למנייה חישובית שאינן חישוביות.]]
פגשנו שלושה סוגים חשובים של קבוצות: ניתנות להצגה דיופנטית, ניתנות למנייה חישובית, וחישוביות. ברור שכל קבוצה חישובית, ניתנת למנייה חישובית (פשוט משום שזהו תנאי חלש יותר), וגם שכל קבוצה הניתנת להצגה דיופנטית היא ניתנת למנייה חישובית (ההבחנה של דייוויס). 

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

==הצעד השני: הצגות דיופנטיות==

את המושגים שפגשנו קודם לכן אפשר להכליל לקבוצות של זוגות או שלשות של מספרים. למשל, קבוצת זוגות A ניתנת להצגה דיופנטית אם עבור פולינום P במקדמים שלמים, קיים פתרון למשוואה <math>\ P(b_1,b_2,x_1,...,x_n)=0</math> [[אם ורק אם]] ה[[זוג סדור|זוג הסדור]] <math>\ (b_1,b_2)</math> שייך ל- A. ההכללה הפשוטה הזו מאפשרת לדון בהצגות דיופנטיות של ''משוואות'', במקום קבוצות. אפשר 'לקודד' משוואה כדוגמת <math>\ a=b^c</math> בקבוצה <math>\ A = \{(a,b,c)| a=b^c\}</math>, ולומר שהמשוואה ניתנת להצגה (פולינומית) דיופנטית אם ורק אם הקבוצה מקיימת תכונה זו.

נזכיר שדייוויס שיער כי כל קבוצה הניתנת למנייה חישובית, אפשר להציג דיופנטית. 
ב-[[1952]] תקפה [[ג'וליה רובינסון]] את הבעיה 'מלמטה', על ידי בחינה של דוגמאות מוכרות של קבוצות הניתנות למנייה חישובית. בפרט היא ניסתה למצוא הצגות דיופנטיות למשוואות <math>\ x=y^z</math> (פונקציית החזקה), <math>\ x=y!</math> (פונקציית ה[[עצרת (מתמטיקה)|עצרת]]), ולקבוצת [[מספר ראשוני|המספרים הראשוניים]]. משימה זו לא צלחה בידה, אולם היא הצליחה להוכיח שניתן יהיה למצוא הצגה דיופנטית לכל המשוואות (או הקבוצות האלה), ברגע שתימצא הצגה דיופנטית ולו לפונקציה אחת הגדלה בקצב מעריכי. לימים הייתה רובינסון, שזכתה ב[[עמיתי מקארתור|מלגת מק'ארתור]], המתמטיקאית הראשונה שנבחרה ל[[האקדמיה הלאומית למדעים (ארצות הברית)|אקדמיה הלאומית למדעים של ארצות הברית]], והנשיאה האישה הראשונה של [[החברה האמריקאית למתמטיקה]].

==הצעד השלישי: הצגות דיופנטיות מעריכיות==

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

==הצעד הרביעי והאחרון: הצגה דיופנטית של משוואות מעריכיות==

[[תמונה:Hilbert 10th problem - 2.jpg|שמאל|ממוזער|280px|השלמת ההוכחה: האלגוריתם שביקש הילברט אינו קיים]]
לאור התוצאות הקודמות של רובינסון, נשאר להציג [[פונקציה מעריכית]] אחת. מכאן ייצא שאפשר להציג פולינומית את כל הפונקציות המעריכיות, ובעזרת אלה אנו יודעים כבר שאפשר להציג כל קבוצה הניתנת למנייה חישובית. כך יתקבל אישור להשערת דייוויס, שכל קבוצה הניתנת למנייה חישובית אפשר להציג על ידי פולינום דיופנטי, ואם נציג קבוצה שאינה חישובית נקבל מיד שהאלגוריתם שביקש הילברט לא יכול להתקיים.

המכה בפטיש היה יורי מאטיאשביץ', שהוכיח ב-[[1972]] כי המשוואה <math>\ m = F_{2n}</math> ניתנת להצגה דיופנטית פולינומית. כאן <math>\ F_{n}</math> הם המספרים ב[[סדרת פיבונאצ'י]], שגדלה כידוע בקצב מעריכי. מסקנה: לא קיים אלגוריתם שיכריע בשאלת הפתירות של משוואה דיופנטית.

==הכללות==
מן העבודה של מאטיאשביץ' נובע כאמור שכל קבוצת מספרים הניתנת למנייה חישובית אפשר להציג באמצעות פולינום דיופנטי. בעבודות אחרות, בעיקר שלו ושל רובינסון, נקבעו חסמים על הגודל של הפולינום הדרוש. כך למשל אפשר תמיד להסתפק בפולינום בתשעה נעלמים (שמעלתו עשויה להמריא עד ל-<math>10^{46}</math>). מן העבר השני אפשר להסתפק בפולינום ממעלה 4, אלא שאז נדרשים עד 58 נעלמים.

לשאלתו המקורית של הילברט, האם קיים אלגוריתם שיכריע בשאלת קיום פתרון ב'''שלמים''' למשוואה פולינומית במקדמים שלמים, התשובה היא אם כן שלילית. את אותה שאלה אפשר לשאול גם על חוגים אחרים: בהינתן [[חוג (מבנה אלגברי)|חוג קומוטטיבי]] R (עם הצגה אלגוריתמית של תת-קבוצה גדולה מספיק), האם אפשר להכריע בשאלת הקיום של פתרון ב-R למערכת משוואות שמקדמיהן ב-R?

היום ידוע, למשל, שאין אלגוריתם שיכריע לאלו משוואות דיופנטיות יש פתרון מעל:
* [[חוג שלמים|חוגי שלמים]] של [[שדה גלובלי|שדות גלובליים]] שיש להם לכל היותר זוג אחד של שיכונים מרוכבים;
* שדות גלובליים מ[[מאפיין של שדה|מאפיין]] חיובי{{הערה|1=Alexandra Shlapentokh, '''Hilbert's Tenth Problem: Diophantine Classes and Extensions to Global Fields'''}} (כגון <math>\ \mathbb{F}_q(t)</math> כאשר <math>\mathbb{F}_q</math> [[שדה סופי]]).
* שדה הפונקציות הרציונליות במשתנה אחד מעל [[שדה המספרים הממשיים|הממשיים]];
* שדה הפונקציות הרציונליות ב- <math>n \geq 2</math> משתנים מעל [[שדה המספרים המרוכבים|המרוכבים]].

מאידך, קיים אלגוריתם הכרעה לבעיות דומות מעל:
* כל שדה סופי (כמובן);
* שדה המספרים הממשיים ושדה המספרים המרוכבים;
* ה[[שדה מקומי|שדות המקומיים]] ממאפיין 0.

אלא שזה אינו סוף הסיפור. עדיין לא ידוע אם יש אלגוריתם הכרעה בכמה מקרים חשובים אחרים:
* משוואות עם מקדמים רציונליים (או מכל [[שדה מספרים]] אחר);
* משוואות עם מקדמים משדה הפונקציות הרציונליות במשתנה אחד מעל המרוכבים;
* ומשוואות עם מקדמים בשדה מקומי ממאפיין חיובי (היינו <math>\mathbb{F}_q((t))</math>).

== לקריאה נוספת ==
{{ltr|
* Bjorn Poonen, '''Undecidability in Number Theory''', Notices of the American Mathematical Society, 55(3), March 2008
* Yuri V. Matiyasevich, '''Hilbert's Tenth Problem''', [[MIT Press]], Cambridge, Massachusetts, 1993
}}

==קישורים חיצוניים==
<div class="mw-content-ltr">
* {{JSTOR|Martin Davis, Reuben Hersh|Hilbert's 10th Problem|24923245|Scientific American|229 (5): 84–91}}
* {{JSTOR|J. P. Jones, Y. V. Matijasevic|Proof of Recursive Unsolvability of Hilbert's Tenth Problem|2324421|American Mathematical Monthly|Vol. 98, No. 8 (October 1991), pp. 689-709}}
</div>
==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}
{{23 הבעיות של הילברט}}
{{בקרת זהויות}}

[[קטגוריה:תורת המספרים]]
[[קטגוריה:הבעיות של הילברט|10]]
[[קטגוריה:משוואות דיופנטיות]]
[[קטגוריה:בעיות לא כריעות במתמטיקה]]
[[קטגוריה:בעיות שאינן ניתנות לחישוב]]
[[קטגוריה:בעיות לא פתירות במתמטיקה]]
[[קטגוריה:משפטי אי היתכנות]]