مسئله دهم هیلبرت
مسئله دهم هیلبرت جزء لیست مسائل هیلبرت است که در سال ۱۹۰۰ مطرح شده‌است. صورت این مسئله چنین است: آیا یک الگوریتم برای تعیین حل پذیری معادلات سیاله با ضرایب عددی گویا و هر تعداد مجهول وجود دارد؟ یعنی فرایندی ابداع شود که بر اساس آن بتوان یک تعداد متناهی از عملگرها را مشخص کرد تا معادله با اعداد صحیح گویا قابل حل باشد. معادله سیاله به قرار زیر است: P یک چندجمله‌ای با ضرایب صحیح است. سال‌های بسیاری طول کشید تا این مسئله بالاخره با پاسخ منفی حل شد. امروزه دانسته شده‌است که مسئله‌ای با چنین الگوریتمی در حالت کلی وجود ندارد. این نتیجه حاصل فعالیت گروهی مارتین دیویس، یوری ماتیاسوویچ، هیلاری پاتنم و جولیا رابینسون بوده‌است.
واژه‌های "فرایند" و "تعداد متناهی عملگرهاً برای توضیح سؤال هیلبرت درمورد الگوریتم به کار رفته‌است. واژه " عدد صحیح" به اعدادی بر می‌گردد که صحیح، مثبت یا منفی یا صفر باشند مثل: ۰، ±۱، ±۲، …. پس هیلبرت به دنبال یک الگوریتم کلی است تا بتواند ادعا کند که داده‌های چندجمله‌ای دیوفانتی با ضرایب صحیح در اعداد صحیح جواب دارند. اکنون پاسخ به این مسئله منفی است: چنین الگوریتمی به‌طور کلی نمی‌تواند وجود داشته باشد، بر خلاف هیلبرت که به امکان وجود آن معتقد بود. قبل از رفتن به سراغ لیست مسائل، وی چنین اظهار می‌دارد: " گاهی ما با داشتن فرضیه‌های غلط به دنبال پاسخ به مسائل هستیم و به خاطر همین موفق نمی‌شویم و مسئلهٔ اثبات غیرممکن بودن حل، تحت فرضهای داده شده ظاهر می‌شود ." کار بر روی این مسئله برای یافتن راه حل بر اساس اعداد طبیعی بوده‌است نه تمام اعداد صحیح، اما به سادگی می‌توان دریافت که الگوریتم درهر دو حالت می‌تواند برای دیگری به کار رود. اگر مشخص شود یکی از الگوریتم‌ها با اعداد طبیعی قابل حل است، این می‌تواند برای مشخص کردن اینکه آیا معادلهٔ n مجهولی با قراردادن الگوریتم مفروض در 2 معادله دارای پاسخ صحیح است. برعکس، یک الگوریتم برای تست کردن حل پذیری، با اعداد صحیح دلخواه، با به کارگیری الگوریتم مفروض برای معادلهٔ حاصل از جایگزینی هر مجهول در معادلهٔ داده شده به وسیلهٔ مجموع مربعات چهار مجهول جدیدمی تواند برای اینکه معادلهٔ داده شده با اعداد طبیعی حل پذیر است استفاده شود. این کار بر اساس قضیه چهار مجذور لاگرانژ است تا نشان دهد که تمام اعداد طبیعی می‌توانند به صورت مجموع چهار مجذور نوشته شود.
مجموعه‌هایی از اعداد طبیعی، دوتایی‌های طبیعی یا حتی formula_4 تایی‌های طبیعی، که تعریف دیوفانتی دارند به عنوان مجموعه‌های دیوفانتی شناخته می‌شوند. تعاریف دیوفانتی می‌توانند به وسیلهٔ دستگاه معادلات و همین‌طور تک معادله‌ها ارائه شوند، زیرا سیستم زیر: هم ارز است با این معادله:
مجموعه‌های شمارای بازگشتی می‌توانند بدین گونه توصیف شوند که برای هر کدام از آن‌ها الگوریتمی وجود دارد، که هنگامی که عددی از اعداد داده شده به عنوان ورودی قرار گیرد این الگوریتم بعد از مدتی می‌ایستد. اما زمانی که از اعداد غیر عضو در این مجموعه به عنوان ورودی قرار بگیرد به سمت بی‌نهایت میل می‌کند. این همان گسترش یافته نظریه محاسبه پذیری است (که به عنوان نظریه بازگشت نیز شناخته می‌شود) که توضیح دقیقی بر درک مفهوم محاسبه پذیری الگوریتم ارائه می‌کند، بدین سان ایجاد مفهوم بازگشتی غیرقابل شمارش و بی‌نهایت، مشکل است. واضح است که مجموعه‌های دیوفانتی، بازگشتی و قابل شمارش‌اند. این مسئله به این دلیل است که می‌توان تمام چند تایی‌های ممکن از مجهولات را در یک دنباله مرتب کرده و سپس برای هر یک از مقادیر داده شده از پارامترها، یکی پس از دیگری این چند تایی‌ها را امتحان کرد تا ببینیم آیا پاسخ معادله هستند یا خیر. غیرقابل حل بودن مسئله دهم هیلبرت نتیجه شگفت‌انگیز این واقعیت است که عکس این مسئله صحیح است یعنی: "هر مجموعه بازگشتی قابل شمارش دیوفانتی است." این نتیجه به نام تئوری ماتیاسویچ (به این دلیل که با ارائه یک مرحله این اثبات را کامل کرد) و نظریهMRDP (از ابتدای نام‌های افراد زیر گرفته شده‌است: یوری ماتیاسویچ، جولیا رابینسون، مارتین دیویس، و هیلاری پاتنام) شناخته شده‌است. از این جهت که مجموعهٔ بازگشتی قابل شمارش نیست، غیرقابل حل بودن مسئله دهم هیلبرت به آسانی نتیجه می‌شود. این را بدین گونه می‌توان گفت که در اینجا یک چندجمله‌ای با ضرایب صحیح به گونه‌ای که مجموعه مقادیر formula_8 برای معادلهٔ که دارای جوابهایی در اعداد طبیعی است، غیرقابل محاسبه است؛ بنابراین نه تنها یک الگوریتم کلی برای آزمایش قابل حل بودن معادلات دیافونتی وجود ندارد، بلکه برای این خانواده از معادلات هیچ الگوریتمی وجود ندارد.
قضیه ماتیاسویچ/ ام آردی پی دو مفهوم را به یکدیگر مرتبط می‌کند- یکی نظریه قابل شمارش بودن و دیگری نظریه اعداد- و دارای چند نتیجه شگفت‌انگیز است. شاید یکی از شگفت‌انگیزترین این نتایج وجود یک معادله دیوفانتی کلی باشد: درستی این روش به سادگی قابل مشاهده است چرا که ماشین‌های تورینگ قابلیت اجرای هر الگوریتمی را دارند. هیلاری پاتنام نشان داد که برای هر مجموعه دیوفانتی S از اعداد صحیح مثبت، چندجمله‌ای وجود دارد به‌طوری‌که در آن S دقیقاً شامل اعداد مثبتی هستند که در بین مقادیر q بردشان مانند همهٔ اعداد طبیعی است. این موضوع می‌تواند در ادامه دیده شود: اگر نشان دهنده تعریف دیوفانتی S باشد، پس کافی است که بنا بر این به عنوان مثال، یک چندجمله‌ای وجود دارد که قسمت مثبت بردش دقیقاً اعداد اول باشند. (از طرفی هیچ چندجمله‌ای نمی‌تواند فقط اعداد اول را بدهد) کاربرد دیگر آن دربارهٔ چیزی است که منطق دانان از آن‌ها به نام گزاره‌های formula_18 یاد می‌کنند، یا برخی مواقع از آن به عنوان گزاره‌های گلدباخ نام برده می‌شود. این‌ها شبیه حدس گلدباخ هستند، اظهار می‌دارد که تمام اعداد طبیعی دارای خاصیتی هستند که قابلیت بررسی الگوریتیمیک برای هر عدد خاص را دارا هستند. قضیه ماتیاسویچ/MRDP نشان می‌دهد که این گونه گزاره‌ها هم ارز این حکم هستند که برخی ازمعادلات دیوفانتی هیچ گونه پاسخی در اعداد طبیعی ندارند. تعدادی از مسائل مهم به این شکل هستند: قضیهٔ آخر فرما، فرضیه ریمان، و قضیه چهار رنگ؛ بعلاوه ادعای اینکه برخی از سیستم‌های قراردادی مثل حساب پئانو یا ZFC می‌توانند به شکل جملات formula_18 توضیح داده شوند. ایده این است که نشان داده شود کارت گودل در کد گذاری اثباتها به وسیلهٔ اعداد طبیعی به روشی است که مشخصه اش قابلیت بررسی پذیری یک اثبات به وسیلهٔ عددی که به نمایندگی از آن اثبات آمده می‌باشد. جملات formula_18 دارای خاصیت ویژه‌ای هستند از این قرار که اگر آن‌ها نادرست باشند، آن حقیقت درهر نوع سیستم صوری معمولی قابل اثبات است. این موضوع به این دلیل است که اشتباه مقادیر در مثال نقض را بتوان به سادگی بررسی کرد. پس اگر یک جملهٔ formula_18 طوری باشد که نه خودش و نه نقیضش در یکی از این سیستم‌ها قابل اثبات باشد پس جمله باید درست باشد. همچنین نتیجه قضیه ماتیاسویچ/MRDP، یک شکل خاص از قضیه ناتمامیت گودل است: "فرض کنید" هیچ جوابی در اعداد طبیعی نداشته باشد. پس یک عدد n وجود دارد که در خروجی A نیست و در حقیقت معادلهٔ هیچ جوابی در اعداد طبیعی ندارد. برای اینکه ببینیم این قضیه درست است، کافی است توجه کنیم که اگر هیچ عددی مثل n نباشد، می‌توان به صورت الگوریتمی عضویت عدد در این مجموعه نا شمارا را هم‌زمان با اجرای الگوریتمA بررسی کنیم تا ببینیم آیا در خروجی هست؟ و هم‌زمان تمام k-تایی‌های ممکن از اعداد طبیعی برای یافتن جواب معادله را برررسی کنیم: ما می‌توانیم یک الگوریتم A را با هر سیستم طبیعی صوری (مثل حساب پئانو یا ZFC) با فرض تولید سیستماتیک نتایج از اصول موضوعه مرتبط کنیم و سپس عدد n را هرگاه یک جمله‌ای به فرم زیر تولید گردد بدست آوریم: پس این قضیه به ما می‌گوید که در این سیستم ممکن است حتی عبارتی با این شکل اگر چه غلط اما ثابت شده باشد؛ یا عبارتی درست همچنان بدون اثبات باقی‌مانده باشد.
ما می‌توانیم از درجه یک مجموعه دیوفانتی به عنوان کوچکترین درجهٔ چندجمله ای یی که معادلهٔ معرّف مجموعه است، صحبت کنیم. به‌طور مشابه ما می‌توانیم بُعد یک چنین مجموعه‌ای را به صورت کمترین تعداد از مجهولات در تعریف معادله مطرح کنیم. به دلیل وجود یک معادله کلی دیوفانتی، مشخص است که کرانه‌های بالایی مطلقی برای هر دوی این معادلات وجود دارد و علاقه بسیاری نیز برای مشخص کردن این کرانه‌ها وجود دارد. در دهه ۱۹۲۰ تورالف اسکولم نشان داد که هر معادله دیوفانتی با یک معادله از درجهٔ چهار یا کمتر هم ارز است. تلاش وی این بود که مجهولات جدیدی را با استفاده از معادلات طوری معرفی کند که آن‌ها با مربع یکی از مجهولات یا حاصلضرب دو مجهول برابر باشند. تکرار این فرایند در یک دستگاه معادلات درجه دوم نتیجه داد، و سپس یک معادله درجه چهارم، با جمع مربع‌ها بدست آمد. پس هر مجموعه دیوفانتی معمولاً از درجه چهار یا کمتر است. البته هنوز مشخص نیست که آیا این بهترین نتیجهٔ ممکن است یا خیر. جولیا رابینسون و یوری ماتیاسویچ نشان دادند که هر مجموعه دیوفانتی یک بعد دارد که بیشتر از ۱۳ نیست. بعدها ماتیاسویچ نشان داد که ۹ مجهول هم کافی است. هرچند این نتیجه نیز ممکن است بهترین نتیجه نباشد، اما هنوز پیشرفت دیگری در این زمینه وجود ندارد هنوز هیچ الگوریتمی برای تست کردن معادلات دیوفانتی با ۹ مجهول یا کمتر در دامنهٔ اعداد وجود ندارد. در مورد پاسخ‌های گویای صحیح (مثل آنچه که هیلبرت خود آن را مطرح کرد) روش چهار مربع نشان می‌دهد که هیج الگوریتمی برای معادلات با تعداد کوچکتر مساوی ۳۶ مجهول وجود ندارد. اما زی وی سان نشان داد که این مسئله برای اعداد صحیح حتی برای معادلات با تعداد کوچکتر مساوی ۱۱ مجهول نیز قابل حل نیستند. مارتین دیویس معادلات الگوریتمی ای که شامل تعدادی از پاسخ‌های معادله دیوفانتی بودند را بررسی کرد. مسئله دهم هیلبرت به دنبال این است که آن عدد ۰ است یا نه. فرض کنید formula_26 و فرض کنید formula_27 یک زیر مجموعهٔ ناتهی خاص از formula_28 باشد. دیویس ثابت کرد که هیچ الگورتیمی برای آزمایش یک معادله دیوفانتی داده شده جهت مشخص کردن اینکه آیا تعداد پاسخ‌های آن عضو مجموعه formula_27 هستند یا خیر وجود ندارد. بنابراین هیچ الگوریتمی وجود ندارد تا نشان دهد تعداد پاسخ‌های این معادله دیوفانتی متناهی، فرد، مربع کامل، عدد اول و یا… هست یا نه.
هرچند هیلبرت این مسئله را برای اعداد گویای صحیح مطرح کرد، اما مطرح کردن آن برای خیلی از حلقه‌ها می‌تواند مفید باشد (مخصوصاً برای هر حلقه‌ای که اعضای آن قابل فهرست کردن باشد). مثال‌های واضح آن حلقه‌های اعداد صحیح در میدان‌های اعداد جبری و همچنین اعداد گویا هستند. یک الگوریتیم مانند چیزی که وی به دنبال آن بود می‌تواند برای پوشاندن دامنه‌های دیگر بسط داده شود. به عنوان مثال معادله زیر: وقتی که formula_31 یک چندجمله‌ای با درجه d باشد، در اعداد گویای غیر منفی قابل حل است اگر و تنها اگر:formula_32 در اعداد طبیعی قابل حل باشد. (اگر کسی یک الگوریتیم داشته باشد تا بتواند قابل حل بودن در اعداد گویای غیر منفی را نشان دهد، به راحتی می‌تواند قابل حل بودن آن را در اعداد گویا نیز نشان دهد) به هر حال دانستن اینکه چنین الگوریتیمی که هیلبرت آرزویش را داشت وجود ندارد، چیزی پیرامون زمینه‌های دیگر نمی‌گوید. کارهای بسیاری پیرامون مسئله دهم هیلبرت برای حلقه‌های صحیح از میدان‌های اعداد جبری انجام گرفته‌است. بر اساس کارهای اولیهٔ جان دنف و لئونارد لیپسچیتز و با استفاده از نظریهٔ class field هارولد ان شاپیرو و الکساندر شاپینتاخ توانستند اثبات کنند: "مسئله دهم هیلبرت برای حلقه‌های صحیح از هر میدان اعداد جبری که گروه گالوا روی اعداد گویا آبلی اند غیرقابل حل‌اند." شلاپینتاخ و ثاناسیس فیداس (مستقل از یکدیگر) به نتیجه یکسانی در زمینهٔ میدان‌های اعداد جبری دست یافتند و آن پذیرفتن یک زوج مزدوج مختلط تعبیه شده‌است. مسئله حلقه اعداد صحیح از میدان‌های اعداد جبری به غیر از نتایجی که در بالا مطرح شد هنوز برای پاسخ گویی باز است. همچنین با وجود تلاش‌های بسیار، مسئله معادلات در اعداد گویا نیز هنوز برای پاسخ گویی باز است. باری مازور حدس زده که برای هر متغیری در اعداد گویا، بستار توپولوژیکی روی اعداد حقیقی از مجموعه جواب‌ها، دارای مؤلفه‌های زیاد اما متناهی است. این حدس می‌گوید که اعداد صحیح روی اعداد گویا دیوفانتی نیستند و همچنین اگر این حدس درست باشد، پاسخ منفی به مسئلهٔ دهم هیلبرت مستلزم رویکردی متفاوت برای حلقه‌های دیگر است.