הבעיה העשירית של הילברט – לכל דבר טוב (חסום) יש סוף

בשעה טובה הגענו אל המכשול האחרון שעומד בינינו ובין סיום ההוכחה שהבעיה העשירית של הילברט אינה כריעה – כמת אוניברסלי חסום. אם נצליח להראות שבהינתן ביטוי דיופנטי $latex P$ אפשר להוכיח שגם הביטוי $latex \forall x<n\left(P\right)$ הוא דיופנטי, נסיים. כאן אמורה להיכנס לתמונה העובדה שהוכחנו (בדם יזע ודמעות) שהפונקציה האקספוננציאלית היא דיופנטית. בואו נתחיל בלראות …

הבעיה העשירית של הילברט – נקמתן של הפונקציות הרקורסיביות והדיופנטיות

בפוסטים הקודמים בסדרה עבדנו קשה כדי להוכיח שהפונקציה האקספוננציאלית היא דיופנטית. הצלחנו בזה סוף סוף ועכשיו אפשר לשכוח מהעניין לבינתיים ולנסות להיזכר מה בעצם אנחנו מנסים להוכיח, ומה האסטרטגיה הכללית שלנו. כזכור, פונקציה דיופנטית היא פונקציה $latex f\left(x_{1},\dots,x_{n}\right)$ כך שקיימת מערכת משוואות דיופנטיות עם המשתנים $latex x_{1},\dots,x_{n},y,z_{1},\dots,z_{n}$ בעלת התכונה הבאה: אם אנו מציבים ערכים $latex …

הבעיה העשירית של הילברט – הפונקציה האקספוננציאלית היא דיופנטית

סוף סוף הגענו אל האקשן האמיתי. כזכור, עבור $latex a>1$ הגדרנו את משוואת פל $latex x^{2}-dy^{2}=1$ כאשר $latex d=a^{2}-1$, וסימנו בתור $latex x_{n}\left(a\right)$ את סדרת ערכי ה-$latex x$-ים של פתרונות של המשוואה (כשכולם מוצגים בתור "חזקות" של הפתרון היסודי). המטרה שלנו כרגע היא להראות שהפונקציה $latex f\left(a,k\right)=x_{k}\left(a\right)$ היא דיופנטית; לשם כך נציג מערכת משוואות שבה …

הבעיה העשירית של הילברט – איך משוואת פל קשורה לכל העניין?

בואו נחזור לדבר על הבעיה העשירית של הילברט שעזבתי בשיא המתח – בדיוק לפני החלק הטכני ביותר, שנתחיל לטפל בו הפעם. תזכורת קטנה למי שאין לו כוח לקרוא את הפוסטים הקודמים: המטרה שלנו היא להוכיח שהפונקציה $latex f\left(n,k\right)=n^{k}$ – "הפונקציה האקספוננציאלית" – היא דיופנטית. כלומר, שקיימת מערכת של משוואות פולינומיות בשלמים עם המון משתנים ששלושה …

הבעיה העשירית של הילברט – איך מקודדים דיופנטית את כל הסדרות הסופיות?

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

הבעיה העשירית של הילברט – פונקציות דיופנטיות וחיות אחרות (רקורסיביות)

אנו ממשיכים בדרך שלנו אל ההוכחה שלא קיים אלגוריתם שפותר את הבעיה העשירית של הילברט. אני מניח שקראתם את פוסט המבוא ולכן קופץ ישר לעניינים הפעם. המושג המרכזי בפוסט הקודם היה קבוצה דיופנטית. זוהי קבוצה $latex S=\left\{ \left(a_{1},\dots,a_{n}\right)\right\} $ של $latex n$-יות של מספרים טבעיים חיוביים, כך שקיים פולינום $latex p\left(x_{1},\dots,x_{n},y_{1},\dots,y_{m}\right)$ בעל התכונה הבאה: למשוואה …

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

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