مسئله دهم هیلبرت
مسئله دهم هیلبرت جزء لیست مسائل هیلبرت است که در سال ۱۹۰۰ مطرح شدهاست. صورت این مسئله چنین است: آیا یک الگوریتم برای تعیین حل پذیری معادلات سیاله با ضرایب عددی گویا و هر تعداد مجهول وجود دارد؟ یعنی فرایندی ابداع شود که بر اساس آن بتوان یک تعداد متناهی از عملگرها را مشخص کرد تا معادله با اعداد صحیح گویا قابل حل باشد. معادله سیاله به قرار زیر است:
P یک چندجملهای با ضرایب صحیح است. سالهای بسیاری طول کشید تا این مسئله بالاخره با پاسخ منفی حل شد. امروزه دانسته شدهاست که مسئلهای با چنین الگوریتمی در حالت کلی وجود ندارد. این نتیجه حاصل فعالیت گروهی مارتین دیویس، یوری ماتیاسوویچ، هیلاری پاتنم و جولیا رابینسون بودهاست.
فرمول سازی
واژههای "فرایند" و "تعداد متناهی عملگرهاً برای توضیح سؤال هیلبرت درمورد الگوریتم به کار رفتهاست. واژه " عدد صحیح" به اعدادی بر میگردد که صحیح، مثبت یا منفی یا صفر باشند مثل: ۰، ±۱، ±۲، …. پس هیلبرت به دنبال یک الگوریتم کلی است تا بتواند ادعا کند که دادههای چندجملهای دیوفانتی با ضرایب صحیح در اعداد صحیح جواب دارند. اکنون پاسخ به این مسئله منفی است: چنین الگوریتمی بهطور کلی نمیتواند وجود داشته باشد، بر خلاف هیلبرت که به امکان وجود آن معتقد بود. قبل از رفتن به سراغ لیست مسائل، وی چنین اظهار میدارد: " گاهی ما با داشتن فرضیههای غلط به دنبال پاسخ به مسائل هستیم و به خاطر همین موفق نمیشویم و مسئلهٔ اثبات غیرممکن بودن حل، تحت فرضهای داده شده ظاهر میشود ." کار بر روی این مسئله برای یافتن راه حل بر اساس اعداد طبیعی بودهاست نه تمام اعداد صحیح، اما به سادگی میتوان دریافت که الگوریتم درهر دو حالت میتواند برای دیگری به کار رود. اگر مشخص شود یکی از الگوریتمها با اعداد طبیعی قابل حل است، این میتواند برای مشخص کردن اینکه آیا معادلهٔ n مجهولی
با قراردادن الگوریتم مفروض در 2 معادله دارای پاسخ صحیح است.
برعکس، یک الگوریتم برای تست کردن حل پذیری، با اعداد صحیح دلخواه، با به کارگیری الگوریتم مفروض برای معادلهٔ حاصل از جایگزینی هر مجهول در معادلهٔ داده شده به وسیلهٔ مجموع مربعات چهار مجهول جدیدمی تواند برای اینکه معادلهٔ داده شده با اعداد طبیعی حل پذیر است استفاده شود. این کار بر اساس قضیه چهار مجذور لاگرانژ است تا نشان دهد که تمام اعداد طبیعی میتوانند به صورت مجموع چهار مجذور نوشته شود.
مجموعههای دیوفانتی
مجموعههایی از اعداد طبیعی، دوتاییهای طبیعی یا حتی
هم ارز است با این معادله:
مجموعههای شمارای بازگشتی میتوانند بدین گونه توصیف شوند که برای هر کدام از آنها الگوریتمی وجود دارد، که هنگامی که عددی از اعداد داده شده به عنوان ورودی قرار گیرد این الگوریتم بعد از مدتی میایستد. اما زمانی که از اعداد غیر عضو در این مجموعه به عنوان ورودی قرار بگیرد به سمت بینهایت میل میکند. این همان گسترش یافته نظریه محاسبه پذیری است (که به عنوان نظریه بازگشت نیز شناخته میشود) که توضیح دقیقی بر درک مفهوم محاسبه پذیری الگوریتم ارائه میکند، بدین سان ایجاد مفهوم بازگشتی غیرقابل شمارش و بینهایت، مشکل است. واضح است که مجموعههای دیوفانتی، بازگشتی و قابل شمارشاند. این مسئله به این دلیل است که میتوان تمام چند تاییهای ممکن از مجهولات را در یک دنباله مرتب کرده و سپس برای هر یک از مقادیر داده شده از پارامترها، یکی پس از دیگری این چند تاییها را امتحان کرد تا ببینیم آیا پاسخ معادله هستند یا خیر. غیرقابل حل بودن مسئله دهم هیلبرت نتیجه شگفتانگیز این واقعیت است که عکس این مسئله صحیح است یعنی: هر مجموعه بازگشتی قابل شمارش دیوفانتی است. این نتیجه به نام تئوری ماتیاسویچ (به این دلیل که با ارائه یک مرحله این اثبات را کامل کرد) و نظریهMRDP (از ابتدای نامهای افراد زیر گرفته شدهاست: یوری ماتیاسویچ، جولیا رابینسون، مارتین دیویس، و هیلاری پاتنام) شناخته شدهاست. از این جهت که مجموعهٔ بازگشتی قابل شمارش نیست، غیرقابل حل بودن مسئله دهم هیلبرت به آسانی نتیجه میشود. این را بدین گونه میتوان گفت که در اینجا یک چندجملهای با ضرایب صحیح
به گونهای که مجموعه مقادیر
که دارای جوابهایی در اعداد طبیعی است، غیرقابل محاسبه است؛ بنابراین نه تنها یک الگوریتم کلی برای آزمایش قابل حل بودن معادلات دیافونتی وجود ندارد، بلکه برای این خانواده از معادلات هیچ الگوریتمی وجود ندارد.
تاریخچه
سال | رخدادها |
---|---|
۱۹۴۴ | امیل لئون پست اعلام کرد که مسئله دهم هیلبرت "به دنبال اثبات غیر قابل حل پذیری است." |
۱۹۴۹ | مارتین دیویس از روش کارت گودل برای کاربرد قضیه باقیمانده چینی به عنوان روش کد گذاری برای به دست آوردن شکل عادی آن برای مجموعههای بازگشتی قابل شمارش استفاده کردهاست:
جایی که |
۱۹۵۰ | جولیا رابینسون، بیخبر از کار دیویس، و با درک اهمیت موضوع تابع نمایی، تلاش نمود تا ثابت کند که EXP، مجموعهای از سه تاییهای (a,b،c) است که برای هر a=b دیوفانتی ست.
تلاشهای وی به نظریه اش منجر شد (که بعدها به نام J.R معروف شد): و برای هر
او با استفاده از خواص معادله پل، اثبات کرد که J.R نشان میدهد EXP یک دیوفانتی است. در نهایت وی نشان داد که اگر EXP یک دیوفانتی باشد پس ضرایب دو جمله ای، فاکتوریل و اول هستند. |
۱۹۵۹ | دیویس و پاتنام باهمکاری یکدیگر بر روی مجموعههای دیوفانتی نمایی کار کردند: مجموعههایی که با معادلات دیوفانتی قابل توضیح هستند در برخی نماها ممکن است مجهول باشند. استفاده از فرم نرمال دیویس به همراه روشهای رابینسون، و با ادعای این گمان که در اینجا تصاعدهای حسابی طولانی و تصادفی، شامل اعداد اول هستند، اثبات کردند که هر مجموعه بازگشتی قابل شمارش یک دیوفانتی نمایی است و نشان میدهد که مسئله دهم هیلبرت غیرقابل حل است. |
۱۹۶۰ | رابینسون نشان داد که چگونه جلوی حدس و گمانهای اثبات نشده را دربارهٔ تصاعدهای حسابی اعداد اول بگیریم و به شکل قابل توجهی اثبات J.R. را ساده کرد که به عنوان یک فرایند اساسی برای پیشرفتهای آینده قرار گرفت، هر چند شک و تردیدهای زیادی در درست بودن آن وجود دارد. |
۱۹۶۱–۱۹۶۹ | دیویس و پانتام گزارههای متفاوتی را که دلالت بر J.R. یافتند. یوری ماتیاسویچ برخی مسائل ساده از مسئله دهم هیلبرت را منتشر کرد. رابینسون نشان داد که وجود مجموعه دیوفانتی نا متناهی در اعداد اول میتواند برای بنای نظریهٔ J.R. کافی باشد. |
۱۹۷۰ | ماتیاسویچ دستگاهی از ده معادلهٔ درجه اول و دوم که یک تعریف دیوفانتی از مجموعهٔ زوجهای (a,b) را طوری عرضه میکند که
این قضیه را J.R. اثبات کرد و اثبات اینکه تمام مجموعههای بازگشتی، شمارا دیوفانتی هستند را تکمیل نموده و نشان داد که مسئله دهم هیلبرت قابل حل نیست. |
کاربردها
قضیه ماتیاسویچ/ ام آردی پی دو مفهوم را به یکدیگر مرتبط میکند- یکی نظریه قابل شمارش بودن و دیگری نظریه اعداد- و دارای چند نتیجه شگفتانگیز است. شاید یکی از شگفتانگیزترین این نتایج وجود یک معادله دیوفانتی کلی باشد:
- یعنی وجود بهطوریکه، برای هر مجموعه دیوفانتی داده شدهوجود دارد یکبهطوری که
درستی این روش به سادگی قابل مشاهده است چرا که ماشینهای تورینگ قابلیت اجرای هر الگوریتمی را دارند. هیلاری پاتنام نشان داد که برای هر مجموعه دیوفانتی S از اعداد صحیح مثبت، چندجملهای
وجود دارد بهطوریکه در آن S دقیقاً شامل اعداد مثبتی هستند که در بین مقادیر q بردشان مانند
همهٔ اعداد طبیعی است. این موضوع میتواند در ادامه دیده شود: اگر
نشان دهنده تعریف دیوفانتی S باشد، پس کافی است که
بنا بر این به عنوان مثال، یک چندجملهای وجود دارد که قسمت مثبت بردش دقیقاً اعداد اول باشند. (از طرفی هیچ چندجملهای نمیتواند فقط اعداد اول را بدهد)
کاربرد دیگر آن دربارهٔ چیزی است که منطق دانان از آنها به نام گزارههای
هیچ جوابی در اعداد طبیعی نداشته باشد. پس یک عدد n0 وجود دارد که در خروجی A نیست و در حقیقت معادلهٔ
هیچ جوابی در اعداد طبیعی ندارد. برای اینکه ببینیم این قضیه درست است، کافی است توجه کنیم که اگر هیچ عددی مثل n0 نباشد، میتوان به صورت الگوریتمی عضویت عدد در این مجموعه نا شمارا را همزمان با اجرای الگوریتمA بررسی کنیم تا ببینیم آیا در خروجی هست؟ و همزمان تمام k-تاییهای ممکن از اعداد طبیعی برای یافتن جواب معادله را برررسی کنیم:
ما میتوانیم یک الگوریتم A را با هر سیستم طبیعی صوری (مثل حساب پئانو یا ZFC) با فرض تولید سیستماتیک نتایج از اصول موضوعه مرتبط کنیم و سپس عدد n را هرگاه یک جملهای به فرم زیر تولید گردد بدست آوریم:
پس این قضیه به ما میگوید که در این سیستم ممکن است حتی عبارتی با این شکل اگر چه غلط اما ثابت شده باشد؛ یا عبارتی درست همچنان بدون اثبات باقیمانده باشد.
نتایج بیشتر
ما میتوانیم از درجه یک مجموعه دیوفانتی به عنوان کوچکترین درجهٔ چندجمله ای یی که معادلهٔ معرّف مجموعه است، صحبت کنیم. بهطور مشابه ما میتوانیم بُعد یک چنین مجموعهای را به صورت کمترین تعداد از مجهولات در تعریف معادله مطرح کنیم. به دلیل وجود یک معادله کلی دیوفانتی، مشخص است که کرانههای بالایی مطلقی برای هر دوی این معادلات وجود دارد و علاقه بسیاری نیز برای مشخص کردن این کرانهها وجود دارد.
در دهه ۱۹۲۰ تورالف اسکولم نشان داد که هر معادله دیوفانتی با یک معادله از درجهٔ چهار یا کمتر هم ارز است. تلاش وی این بود که مجهولات جدیدی را با استفاده از معادلات طوری معرفی کند که آنها با مربع یکی از مجهولات یا حاصلضرب دو مجهول برابر باشند. تکرار این فرایند در یک دستگاه معادلات درجه دوم نتیجه داد، و سپس یک معادله درجه چهارم، با جمع مربعها بدست آمد. پس هر مجموعه دیوفانتی معمولاً از درجه چهار یا کمتر است. البته هنوز مشخص نیست که آیا این بهترین نتیجهٔ ممکن است یا خیر.
جولیا رابینسون و یوری ماتیاسویچ نشان دادند که هر مجموعه دیوفانتی یک بعد دارد که بیشتر از ۱۳ نیست. بعدها ماتیاسویچ نشان داد که ۹ مجهول هم کافی است. هرچند این نتیجه نیز ممکن است بهترین نتیجه نباشد، اما هنوز پیشرفت دیگری در این زمینه وجود ندارد هنوز هیچ الگوریتمی برای تست کردن معادلات دیوفانتی با ۹ مجهول یا کمتر در دامنهٔ اعداد وجود ندارد. در مورد پاسخهای گویای صحیح (مثل آنچه که هیلبرت خود آن را مطرح کرد) روش چهار مربع نشان میدهد که هیج الگوریتمی برای معادلات با تعداد کوچکتر مساوی ۳۶ مجهول وجود ندارد. اما زی وی سان نشان داد که این مسئله برای اعداد صحیح حتی برای معادلات با تعداد کوچکتر مساوی ۱۱ مجهول نیز قابل حل نیستند.
مارتین دیویس معادلات الگوریتمی ای که شامل تعدادی از پاسخهای معادله دیوفانتی بودند را بررسی کرد. مسئله دهم هیلبرت به دنبال این است که آن عدد ۰ است یا نه. فرض کنید
تعمیمهای مسئله دهم هیلبرت
هرچند هیلبرت این مسئله را برای اعداد گویای صحیح مطرح کرد، اما مطرح کردن آن برای خیلی از حلقهها میتواند مفید باشد (مخصوصاً برای هر حلقهای که اعضای آن قابل فهرست کردن باشد). مثالهای واضح آن حلقههای اعداد صحیح در میدانهای اعداد جبری و همچنین اعداد گویا هستند. یک الگوریتیم مانند چیزی که وی به دنبال آن بود میتواند برای پوشاندن دامنههای دیگر بسط داده شود. به عنوان مثال معادله زیر:
وقتی که
پینوشتها
- ↑ S. Barry Cooper, Computability theory, p. 98
- ↑ براساس یک باور قدیمی در منطق ریاضیات که0 عدد طبیعی در نظر گرفته میشود، در این مقاله نیز 0 عدد طبیعی در نظر گرفته شدهاست.
- ↑ این حدس توسط بن گرین و ترنس تائو با عنوان قضیه گرین-تائو در سال 2004 ثابت شد.
- ↑ بازبینی نشریه مشترک دیویس، پاتنام و رابینسون در مجله ریاضیات، با رویکرد نادرست بودن جی. آر
- ↑ جملههای درپایینترین ردهٔ سلسه مراتبی قرار دارند که از آنها به نام سلسله مراتب حسابی یاد میشود.<\ref>همچنین حدس گلباخ میتواند این گونه نیز تفسیر شود که هر عدد طبیعی n، مقدار 2n+4 به صورت مجموع دو عدد اول است، که البته یک الگوریتم ساده برای تست این موضوع وجود دارد.
- ↑ همچنین حدس گلباخ میتواند این گونه نیز تفسیر شود که هر عدد طبیعی n، مقدار 2n+4 به صورت مجموع دو عدد اول است، که البته یک الگوریتم ساده برای تست این موضوع وجود دارد.
- ↑ در واقع این همارزی در حساب پئانو قابل اثبات میباشد.
- ↑ در این مورد، حتی عدد 3 نیز نمیتواند از یک کران مطلقاً بالا خارج باشد.
- ↑ http://www-math.mit.edu/~poonen/papers/subrings.pdf
منابع
- Hilbert's tenth problem
- Yuri V. Matiyasevich, Hilbert's Tenth Problem, انتشارات امآیتی، Cambridge, Massachusetts, 1993.
- Davis, Martin; Matiyasevich, Yuri; Robinson, Julia (1976). "Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a Negative Solution". In Felix E. Browder (ed.). Mathematical Developments Arising from Hilbert Problems. Proceedings of Symposia in Pure Mathematics. Vol. XXVIII.2. American Mathematical Society. pp. 323–378. ISBN 0-8218-1428-1. Reprinted in The Collected Works of Julia Robinson, سولومون ففرمن، editor, pp. 269–378, American Mathematical Society ۱۹۹۶.
- مارتین دیویس، "Hilbert's Tenth Problem is Unsolvable," American Mathematical Monthly, vol.80(1973), pp. 233–۲۶۹; reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
- مارتین دیویس and Reuben Hersh, "Hilbert's 10th Problem", ساینتیفیک آمریکن, vol. 229 (1973), pp. 84–۹۱.
- Jan Denef, Leonard Lipschitz, Thanases Pheidas, Jan van Geel, editors, "Hilbert's Tenth Problem: Workshop at Ghent University, Belgium, November 2–5, 1999." Contemporary Mathematics vol. 270(2000), American Mathematical Society.
مطالعه بیشتر
- Shlapentokh, Alexandra (2007). Hilbert's tenth problem. Diophantine classes and extensions to global fields. New Mathematical Monographs. Vol. 7. Cambridge: Cambridge University Press. ISBN 0-521-83360-4. Zbl ۱۱۹۶٫۱۱۱۶۶.
{{}}
: Check|zbl=
value (help)
پیوند به بیرون
- Hilbert's Tenth Problem: a History of Mathematical Discovery
- Hilbert's Tenth Problem page!
- Zhi Wei Sun: On Hilbert's Tenth Problem and Related Topics
- Trailer for Julia Robinson and Hilbert's Tenth Problem در یوتیوب