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

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

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

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

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

סוף סוף הגענו אל האקשן האמיתי. כזכור, עבור $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(n,k\right)=n^{k}$ – "הפונקציה … להמשיך לקרוא

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

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

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

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

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

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