مسئله دهم هیلبرت

مسئله دهم هیلبرت جزء لیست مسائل هیلبرت است که در سال ۱۹۰۰ مطرح شده‌است. صورت این مسئله چنین است:
آیا یک الگوریتم برای تعیین حل پذیری معادلات سیاله با ضرایب عددی گویا و هر تعداد مجهول وجود دارد؟ یعنی فرایندی ابداع شود که بر اساس آن بتوان یک تعداد متناهی از عملگرها را مشخص کرد تا معادله با اعداد صحیح گویا قابل حل باشد.
معادله سیاله به قرار زیر است:

P یک چندجمله‌ای با ضرایب صحیح است. سال‌های بسیاری طول کشید تا این مسئله بالاخره با پاسخ منفی حل شد. امروزه دانسته شده‌است که مسئله‌ای با چنین الگوریتمی در حالت کلی وجود ندارد. این نتیجه حاصل فعالیت گروهی مارتین دیویس، یوری ماتیاسوویچ، هیلاری پاتنم و جولیا رابینسون بوده‌است.S. Barry Cooper, Computability theory, p. 98

 فرمول سازی 
واژه‌های "فرایند" و "تعداد متناهی عملگرها برای توضیح سؤال هیلبرت درمورد الگوریتم به کار رفته‌است. واژهٔ "عدد صحیح" به اعدادی بر می‌گردد که صحیح، مثبت یا منفی یا صفر باشند مثل: ۰، ±۱، ±۲، …. پس هیلبرت به دنبال یک الگوریتم کلی است تا بتواند ادعا کند که داده‌های چندجمله‌ای دیوفانتی با ضرایب صحیح در اعداد صحیح جواب دارند. اکنون پاسخ به این مسئله منفی است: چنین الگوریتمی به‌طور کلی نمی‌تواند وجود داشته باشد، برخلاف هیلبرت که به امکان وجود آن معتقد بود. قبل از رفتن به سراغ لیست مسائل، وی چنین اظهار می‌دارد:
" گاهی ما با داشتن فرضیه‌های غلط به دنبال پاسخ به مسائل هستیم و به خاطر همین موفق نمی‌شویم و مسئلهٔ اثبات غیرممکن بودن حل، تحت فرضهای داده شده ظاهر می‌شود ."
کار بر روی این مسئله برای یافتن راه حل بر اساس اعداد طبیعی بوده‌است نه تمام اعداد صحیح،براساس یک باور قدیمی در منطق ریاضیات که0 عدد طبیعی در نظر گرفته می‌شود، در این مقاله نیز 0 عدد طبیعی در نظر گرفته شده‌است. اما به سادگی می‌توان دریافت که الگوریتم درهر دو حالت می‌تواند برای دیگری به کار رود. اگر مشخص شود یکی از الگوریتم‌ها با اعداد طبیعی قابل حل است، این می‌تواند برای مشخص کردن اینکه آیا معادلهٔ n مجهولی

با قراردادن الگوریتم مفروض در 2n معادله دارای پاسخ صحیح است.

برعکس، یک الگوریتم برای تست کردن حل پذیری، با اعداد صحیح دلخواه، با به کارگیری الگوریتم مفروض برای معادلهٔ حاصل از جایگزینی هر مجهول در معادلهٔ داده شده به وسیلهٔ مجموع مربعات چهار مجهول جدیدمی تواند برای اینکه معادلهٔ داده شده با اعداد طبیعی حل پذیر است استفاده شود. این کار بر اساس قضیه چهار مجذور لاگرانژ است تا نشان دهد که تمام اعداد طبیعی می‌توانند به صورت مجموع چهار مجذور نوشته شود.

 مجموعه‌های دیوفانتی 
مجموعه‌هایی از اعداد طبیعی، دوتایی‌های طبیعی یا حتی  تایی‌های طبیعی، که تعریف دیوفانتی دارند به عنوان مجموعه‌های دیوفانتی شناخته می‌شوند. تعاریف دیوفانتی می‌توانند به وسیلهٔ دستگاه معادلات و همین‌طور تک معادله‌ها ارائه شوند، زیرا سیستم زیر:

هم ارز است با این معادله:

مجموعه‌های شمارای بازگشتی می‌توانند بدین گونه توصیف شوند که برای هر کدام از آن‌ها الگوریتمی وجود دارد، که هنگامی که عددی از اعداد داده شده به عنوان ورودی قرار گیرد این الگوریتم بعد از مدتی می‌ایستد. اما زمانی که از اعداد غیر عضو در این مجموعه به عنوان ورودی قرار بگیرد به سمت بی‌نهایت میل می‌کند. این همان گسترش یافته نظریه محاسبه پذیری است (که به عنوان نظریه بازگشت نیز شناخته می‌شود) که توضیح دقیقی بر درک مفهوم محاسبه پذیری الگوریتم ارائه می‌کند، بدین سان ایجاد مفهوم بازگشتی غیرقابل شمارش و بی‌نهایت، مشکل است. واضح است که مجموعه‌های دیوفانتی، بازگشتی و قابل شمارش‌اند. این مسئله به این دلیل است که می‌توان تمام چند تایی‌های ممکن از مجهولات را در یک دنباله مرتب کرده و سپس برای هر یک از مقادیر داده شده از پارامترها، یکی پس از دیگری این چند تایی‌ها را امتحان کرد تا ببینیم آیا پاسخ معادله هستند یا خیر. غیرقابل حل بودن مسئله دهم هیلبرت نتیجه شگفت‌انگیز این واقعیت است که عکس این مسئله صحیح است یعنی:
هر مجموعه بازگشتی قابل شمارش دیوفانتی است.
این نتیجه به نام تئوری ماتیاسویچ (به این دلیل که با ارائه یک مرحله این اثبات را کامل کرد) و نظریهMRDP (از ابتدای نام‌های افراد زیر گرفته شده‌است: یوری ماتیاسویچ، جولیا رابینسون، مارتین دیویس، و هیلاری پاتنام) شناخته شده‌است. از این جهت که مجموعهٔ بازگشتی قابل شمارش نیست، غیرقابل حل بودن مسئله دهم هیلبرت به آسانی نتیجه می‌شود. این را بدین گونه می‌توان گفت که در اینجا یک چندجمله‌ای با ضرایب صحیح

به گونه‌ای که مجموعه مقادیر  برای معادلهٔ

که دارای جوابهایی در اعداد طبیعی است، غیرقابل محاسبه است؛ بنابراین نه تنها یک الگوریتم کلی برای آزمایش قابل حل بودن معادلات دیافونتی وجود ندارد، بلکه برای این خانواده از معادلات هیچ الگوریتمی وجود ندارد.

 تاریخچه 
سالرخدادها۱۹۴۴امیل لئون پست اعلام کرد که مسئله دهم هیلبرت "به دنبال اثبات غیر قابل حل پذیری است."۱۹۴۹مارتین دیویس از روش کارت گودل برای کاربرد قضیه باقی‌مانده چینی به عنوان روش کد گذاری برای به دست آوردن شکل عادی آن برای مجموعه‌های بازگشتی قابل شمارش استفاده کرده‌است:

جایی که   چندجمله‌ای با ضرایب صحیح است.
به‌طور کلی این تنها یک کمیت سنج کلی کران دار است که می‌تواند در تعریف دیوفانتی بگنجد.
با استفاده از یک اثبات آسان و غیر پیچیده، وی توضیح داد که در اینجا یک مجموعه دیوفانتی وجود دارد که متمم آن دیوفانتی نیست. چرا که مجموعه‌های بازگشتی قابل شمارش نیز با متمم‌گیری بسته نمی‌شوند.۱۹۵۰جولیا رابینسون، بی‌خبر از کار دیویس، و با درک اهمیت موضوع تابع نمایی، تلاش نمود تا ثابت کند که EXP، مجموعه‌ای از سه تایی‌های (a,b،c) است که برای هر a=bc دیوفانتی ست.
تلاش‌های وی به نظریه اش منجر شد (که بعدها به نام J.R معروف شد):
یک مجموعه دیوفانتی D از دوتایی (a,b) وجود دارد، به‌طوری که:

و برای هر ،
 به‌طوری‌که 
او با استفاده از خواص معادله پل، اثبات کرد که J.R نشان می‌دهد EXP یک دیوفانتی است. در نهایت وی نشان داد که اگر EXP یک دیوفانتی باشد پس ضرایب دو جمله ای، فاکتوریل و اول هستند.۱۹۵۹دیویس و پاتنام باهمکاری یکدیگر بر روی مجموعه‌های دیوفانتی نمایی کار کردند: مجموعه‌هایی که با معادلات دیوفانتی قابل توضیح هستند در برخی نماها ممکن است مجهول باشند. استفاده از فرم نرمال دیویس به همراه روش‌های رابینسون، و با ادعای این گمان که در اینجا تصاعدهای حسابی طولانی و تصادفی، شامل اعداد اول هستند،این حدس توسط بن گرین و ترنس تائو با عنوان قضیه گرین-تائو در سال 2004 ثابت شد. اثبات کردند که هر مجموعه بازگشتی قابل شمارش یک دیوفانتی نمایی است و نشان می‌دهد که مسئله دهم هیلبرت غیرقابل حل است.۱۹۶۰رابینسون نشان داد که چگونه جلوی حدس و گمان‌های اثبات نشده را دربارهٔ تصاعدهای حسابی اعداد اول بگیریم و به شکل قابل توجهی اثبات J.R. را ساده کرد که به عنوان یک فرایند اساسی برای پیشرفت‌های آینده قرار گرفت، هر چند شک و تردیدهای زیادی در درست بودن آن وجود دارد.بازبینی نشریه مشترک دیویس، پاتنام و رابینسون در مجله ریاضیات، با رویکرد نادرست بودن جی. آر۱۹۶۱–۱۹۶۹دیویس و پانتام گزاره‌های متفاوتی را که دلالت بر J.R. یافتند. یوری ماتیاسویچ برخی مسائل ساده از مسئله دهم هیلبرت را منتشر کرد. رابینسون نشان داد که وجود مجموعه دیوفانتی نا متناهی در اعداد اول می‌تواند برای بنای نظریهٔ J.R. کافی باشد.۱۹۷۰ماتیاسویچ دستگاهی از ده معادلهٔ درجه اول و دوم که یک تعریف دیوفانتی از مجموعهٔ زوج‌های (a,b) را طوری عرضه می‌کند که
 وقتی که  برابر با nامین عدد فیبوناتچی باشد را عرضه داشت.
این قضیه را J.R. اثبات کرد و اثبات اینکه تمام مجموعه‌های بازگشتی، شمارا دیوفانتی هستند را تکمیل نموده و نشان داد که مسئله دهم هیلبرت قابل حل نیست.

 کاربردها 
قضیه ماتیاسویچ/ ام آردی پی دو مفهوم را به یکدیگر مرتبط می‌کند- یکی نظریه قابل شمارش بودن و دیگری نظریه اعداد- و دارای چند نتیجه شگفت‌انگیز است. شاید یکی از شگفت‌انگیزترین این نتایج وجود یک معادله دیوفانتی کلی باشد:
یعنی وجود   به‌طوری‌که، برای هر مجموعه دیوفانتی داده شده  وجود دارد یک  به‌طوری که

درستی این روش به سادگی قابل مشاهده است چرا که ماشین‌های تورینگ قابلیت اجرای هر الگوریتمی را دارند. هیلاری پاتنام نشان داد که برای هر مجموعه دیوفانتی S از اعداد صحیح مثبت، چندجمله‌ای

وجود دارد به‌طوری‌که در آن S دقیقاً شامل اعداد مثبتی هستند که در بین مقادیر q بردشان مانند

همهٔ اعداد طبیعی است. این موضوع می‌تواند در ادامه دیده شود: اگر

نشان دهنده تعریف دیوفانتی S باشد، پس کافی است که

بنا بر این به عنوان مثال، یک چندجمله‌ای وجود دارد که قسمت مثبت بردش دقیقاً اعداد اول باشند. (از طرفی هیچ چندجمله‌ای نمی‌تواند فقط اعداد اول را بدهد)
کاربرد دیگر آن دربارهٔ چیزی است که منطق دانان از آن‌ها به نام گزاره‌های  یاد می‌کنند، یا برخی مواقع از آن به عنوان گزاره‌های گلدباخ نام برده می‌شود.جمله‌های  درپایین‌ترین ردهٔ سلسه مراتبی قرار دارند که از آن‌ها به نام سلسله مراتب حسابی یاد می‌شود.<\ref>همچنین حدس گلباخ می‌تواند این گونه نیز تفسیر شود که هر عدد طبیعی n، مقدار 2n+4 به صورت مجموع دو عدد اول است، که البته یک الگوریتم ساده برای تست این موضوع وجود دارد. این‌ها شبیه حدس گلدباخ هستند، اظهار می‌دارد که تمام اعداد طبیعی دارای خاصیتی هستند که قابلیت بررسی الگوریتیمیک برای هر عدد خاص را دارا هستند.همچنین حدس گلباخ می‌تواند این گونه نیز تفسیر شود که هر عدد طبیعی n، مقدار 2n+4 به صورت مجموع دو عدد اول است، که البته یک الگوریتم ساده برای تست این موضوع وجود دارد. قضیه ماتیاسویچ/MRDP نشان می‌دهد که این گونه گزاره‌ها هم ارز این حکم هستند که برخی ازمعادلات دیوفانتی هیچ گونه پاسخی در اعداد طبیعی ندارند.در واقع این هم‌ارزی در حساب پئانو قابل اثبات می‌باشد.
تعدادی از مسائل مهم به این شکل هستند: قضیهٔ آخر فرما، فرضیه ریمان، و قضیه چهار رنگ؛ به‌علاوه ادعای اینکه برخی از سیستم‌های قراردادی مثل حساب پئانو یا ZFC می‌توانند به شکل جملات  توضیح داده شوند. ایده این است که نشان داده شود کارت گودل در کد گذاری اثباتها به وسیلهٔ اعداد طبیعی به روشی است که مشخصه اش قابلیت بررسی پذیری یک اثبات به وسیلهٔ عددی که به نمایندگی از آن اثبات آمده می‌باشد.
جملات  دارای خاصیت ویژه‌ای هستند از این قرار که اگر آن‌ها نادرست باشند، آن حقیقت درهر نوع سیستم صوری معمولی قابل اثبات است.
این موضوع به این دلیل است که اشتباه مقادیر در مثال نقض را بتوان به سادگی بررسی کرد. پس اگر یک جملهٔ  طوری باشد که نه خودش و نه نقیضش در یکی از این سیستم‌ها قابل اثبات باشد پس جمله باید درست باشد.
همچنین نتیجه قضیه ماتیاسویچ/MRDP، یک شکل خاص از قضیه ناتمامیت گودل است:
فرض کنید

هیچ جوابی در اعداد طبیعی نداشته باشد. پس یک عدد n0 وجود دارد که در خروجی A نیست و در حقیقت معادلهٔ

هیچ جوابی در اعداد طبیعی ندارد.
برای اینکه ببینیم این قضیه درست است، کافی است توجه کنیم که اگر هیچ عددی مثل n0 نباشد، می‌توان به صورت الگوریتمی عضویت عدد در این مجموعه نا شمارا را هم‌زمان با اجرای الگوریتمA بررسی کنیم تا ببینیم آیا در خروجی هست؟ و هم‌زمان تمام k-تایی‌های ممکن از اعداد طبیعی برای یافتن جواب معادله را برررسی کنیم:

ما می‌توانیم یک الگوریتم A را با هر سیستم طبیعی صوری (مثل حساب پئانو یا ZFC) با فرض تولید سیستماتیک نتایج از اصول موضوعه مرتبط کنیم و سپس عدد n را هرگاه یک جمله‌ای به فرم زیر تولید گردد به‌دست آوریم:

پس این قضیه به ما می‌گوید که در این سیستم ممکن است حتی عبارتی با این شکل اگر چه غلط اما ثابت شده باشد؛ یا عبارتی درست همچنان بدون اثبات باقی‌مانده باشد.

 نتایج بیشتر 
ما می‌توانیم از درجه یک مجموعه دیوفانتی به عنوان کوچکترین درجهٔ چندجمله ای یی که معادلهٔ معرّف مجموعه است، صحبت کنیم. به‌طور مشابه ما می‌توانیم بُعد یک چنین مجموعه‌ای را به صورت کمترین تعداد از مجهولات در تعریف معادله مطرح کنیم. به دلیل وجود یک معادله کلی دیوفانتی، مشخص است که کرانه‌های بالایی مطلقی برای هر دوی این معادلات وجود دارد و علاقه بسیاری نیز برای مشخص کردن این کرانه‌ها وجود دارد.
در دهه ۱۹۲۰ تورالف اسکولم نشان داد که هر معادله دیوفانتی با یک معادله از درجهٔ چهار یا کمتر هم ارز است. تلاش وی این بود که مجهولات جدیدی را با استفاده از معادلات طوری معرفی کند که آن‌ها با مربع یکی از مجهولات یا حاصلضرب دو مجهول برابر باشند. تکرار این فرایند در یک دستگاه معادلات درجه دوم نتیجه داد، و سپس یک معادله درجه چهارم، با جمع مربع‌ها به‌دست آمد. پس هر مجموعه دیوفانتی معمولاً از درجه چهار یا کمتر است. البته هنوز مشخص نیست که آیا این بهترین نتیجهٔ ممکن است یا خیر.
جولیا رابینسون و یوری ماتیاسویچ نشان دادند که هر مجموعه دیوفانتی یک بعد دارد که بیشتر از ۱۳ نیست. بعدها ماتیاسویچ نشان داد که ۹ مجهول هم کافی است. هرچند این نتیجه نیز ممکن است بهترین نتیجه نباشد، اما هنوز پیشرفت دیگری در این زمینه وجود ندارددر این مورد، حتی عدد 3 نیز نمی‌تواند از یک کران مطلقاً بالا خارج باشد. هنوز هیچ الگوریتمی برای تست کردن معادلات دیوفانتی با ۹ مجهول یا کمتر در دامنهٔ اعداد وجود ندارد. در مورد پاسخ‌های گویای صحیح (مثل آنچه که هیلبرت خود آن را مطرح کرد) روش چهار مربع نشان می‌دهد که هیج الگوریتمی برای معادلات با تعداد کوچکتر مساوی ۳۶ مجهول وجود ندارد. اما زی وی سان نشان داد که این مسئله برای اعداد صحیح حتی برای معادلات با تعداد کوچکتر مساوی ۱۱ مجهول نیز قابل حل نیستند.
مارتین دیویس معادلات الگوریتمی ای که شامل تعدادی از پاسخ‌های معادله دیوفانتی بودند را بررسی کرد. مسئله دهم هیلبرت به دنبال این است که آن عدد ۰ است یا نه. فرض کنید  و فرض کنید  یک زیر مجموعهٔ ناتهی خاص از  باشد. دیویس ثابت کرد که هیچ الگورتیمی برای آزمایش یک معادله دیوفانتی داده شده جهت مشخص کردن اینکه آیا تعداد پاسخ‌های آن عضو مجموعه  هستند یا خیر وجود ندارد. بنابراین هیچ الگوریتمی وجود ندارد تا نشان دهد تعداد پاسخ‌های این معادله دیوفانتی متناهی، فرد، مربع کامل، عدد اول و یا… هست یا نه.

 تعمیم‌های مسئله دهم هیلبرت 
هرچند هیلبرت این مسئله را برای اعداد گویای صحیح مطرح کرد، اما مطرح کردن آن برای خیلی از حلقه‌ها می‌تواند مفید باشد (مخصوصاً برای هر حلقه‌ای که اعضای آن قابل فهرست کردن باشد). مثال‌های واضح آن حلقه‌های اعداد صحیح در میدان‌های اعداد جبری و همچنین اعداد گویا هستند. یک الگوریتیم مانند چیزی که وی به دنبال آن بود می‌تواند برای پوشاندن دامنه‌های دیگر بسط داده شود. به عنوان مثال معادله زیر:

وقتی که  یک چندجمله‌ای با درجه d باشد، در اعداد گویای غیر منفی قابل حل است اگر و تنها اگر: در اعداد طبیعی قابل حل باشد. (اگر کسی یک الگوریتیم داشته باشد تا بتواند قابل حل بودن در اعداد گویای غیر منفی را نشان دهد، به راحتی می‌تواند قابل حل بودن آن را در اعداد گویا نیز نشان دهد) به هر حال دانستن اینکه چنین الگوریتیمی که هیلبرت آرزویش را داشت وجود ندارد، چیزی پیرامون زمینه‌های دیگر نمی‌گوید.
کارهای بسیاری پیرامون مسئله دهم هیلبرت برای حلقه‌های صحیح از میدان‌های اعداد جبری انجام گرفته‌است. بر اساس کارهای اولیهٔ جان دنف و لئونارد لیپسچیتز و با استفاده از نظریهٔ class field هارولد ان شاپیرو و الکساندر شاپینتاخ توانستند اثبات کنند:
مسئله دهم هیلبرت برای حلقه‌های صحیح از هر میدان اعداد جبری که گروه گالوا روی اعداد گویا آبلی اند غیرقابل حل‌اند.
شلاپینتاخ و ثاناسیس فیداس (مستقل از یکدیگر) به نتیجه یکسانی در زمینهٔ میدان‌های اعداد جبری دست یافتند و آن پذیرفتن یک زوج مزدوج مختلط تعبیه شده‌است.
مسئله حلقه اعداد صحیح از میدان‌های اعداد جبری به غیر از نتایجی که در بالا مطرح شد هنوز برای پاسخ گویی باز است. همچنین با وجود تلاش‌های بسیار، مسئله معادلات در اعداد گویا نیز هنوز برای پاسخ گویی باز است. باری مازور حدس زده که برای هر متغیری در اعداد گویا، بستار توپولوژیکی روی اعداد حقیقی از مجموعه جواب‌ها، دارای مؤلفه‌های زیاد اما متناهی است.http://www-math.mit.edu/~poonen/papers/subrings.pdf
این حدس می‌گوید که اعداد صحیح روی اعداد گویا دیوفانتی نیستند و همچنین اگر این حدس درست باشد، پاسخ منفی به مسئلهٔ دهم هیلبرت مستلزم رویکردی متفاوت برای حلقه‌های دیگر است.

 پی‌نوشت‌ها 

 منابع 
 Hilbert's tenth problem
 Yuri V. Matiyasevich, Hilbert's Tenth Problem, انتشارات ام‌آی‌تی،  Cambridge, Massachusetts, 1993.
  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.

 مطالعه بیشتر 


 پیوند به بیرون 
 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


#۱۰
رده:مسئله‌های تصمیم‌ناپذیر
رده:معادله سیاله