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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

תוכן עניינים

1 הצעד הראשון: הקשר לחישוביות
2 סיכום ביניים
3 הצעד השני: הצגות דיופנטיות
4 הצעד השלישי: הצגות דיופנטיות מעריכיות
5 הצעד הרביעי והאחרון: הצגה דיופנטית של משוואות מעריכיות
6 הכללות
7 מקורות

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

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

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

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

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

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

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

[עריכה] סיכום ביניים

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

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

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

[עריכה] הצעד השני: הצגות דיופנטיות

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

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

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

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

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

השלמת ההוכחה: האלגוריתם שביקש הילברט אינו קיים

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

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

[עריכה] הכללות

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

לשאלתו המקורית של הילברט, האם קיים אלגוריתם שיכריע בשאלת קיום פתרון בשלמים למשוואה פולינומית במקדמים שלמים, התשובה היא אם כן שלילית. בדומה לזה, אין אלגוריתם שיכריע לאלו משוואות דיופנטיות יש פתרון מעל חוגי שלמים של שדות גלובליים, וגם לא מעל שדות גלובליים ממאפיין חיובי ^[1]. אלא שזה אינו סוף הסיפור. נכון ל-2005, עדיין לא ידוע האם קיים אלגוריתם שיכריע באשר לפתרון של משוואות כאלה בשני מקרים חשובים אחרים:

משוואות במספרים רציונליים,
ומשוואות בשדות מקומיים.

[עריכה] מקורות

^ Alexandra Shlapentokh, Hilbert's Tenth Problem: Diophantine Classes and Extensions to Global Fields

מקור: http://he.wikipedia.org../../../%D7%94/%D7%91/%D7%A2/%D7%94%D7%91%D7%A2%D7%99%D7%94_%D7%94%D7%A2%D7%A9%D7%99%D7%A8%D7%99%D7%AA_%D7%A9%D7%9C_%D7%94%D7%99%D7%9C%D7%91%D7%A8%D7%98.html

קטגוריות: תורת המספרים | הבעיות של הילברט

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

מתוך ויקיפדיה, האנציקלופדיה החופשית

תוכן עניינים

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

[עריכה] סיכום ביניים

[עריכה] הצעד השני: הצגות דיופנטיות

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

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

[עריכה] הכללות

[עריכה] מקורות

Views

ניווט

קהילה

חיפוש

שפות אחרות