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

مسئله دهم هیلبرت جزء لیست مسائل هیلبرت است که در سال ۱۹۰۰ مطرح شده‌است. صورت این مسئله چنین است:
آیا یک الگوریتم برای تعیین حل پذیری معادلات سیاله با ضرایب عددی گویا و هر تعداد مجهول وجود دارد؟ یعنی فرایندی ابداع شود که بر اساس آن بتوان یک تعداد متناهی از عملگرها را مشخص کرد تا معادله با اعداد صحیح گویا قابل حل باشد.
معادله سیاله به قرار زیر است:
P یک چندجمله‌ای با ضرایب صحیح است. سالهای بسیاری طول کشید تا این مسئله بالاخره با پاسخ منفی حل شد. امروزه دانسته شده‌است که مسئله‌ای با چنین الگوریتمی در حالت کلی وجود ندارد. این نتیجه حاصل فعالیت گروهی مارتین دیویس، یوری ماتیاسوویچ، هیلاری پاتنم و جولیا رابینسون بوده‌است.
فرمول سازی
واژه‌های "فرایند" و "تعداد متناهی عملگرها برای توضیح سوال هیلبرت درمورد الگوریتم به کار رفته‌است. واژه " عدد صحیح" به اعدادی بر می‌گردد که صحیح، مثبت یا منفی یا صفر باشند مثل: ۰، ±۱، ±۲، …. پس هیلبرت به دنبال یک الگوریتم کلی است تا بتواند ادعا کند که داده‌های چندجمله‌ای دیوفانتی با ضرایب صحیح در اعداد صحیح جواب دارند. اکنون پاسخ به این مسئله منفی است: چنین الگوریتمی به‌طور کلی نمی‌تواند وجود داشته باشد، بر خلاف هیلبرت که به امکان وجود آن معتقد بود. قبل از رفتن به سراغ لیست مسائل، وی چنین اظهار می‌دارد:
" گاهی ما با داشتن فرضیه‌های غلط به دنبال پاسخ به مسائل هستیم و به خاطر همین موفق نمی‌شویم و مسئله اثبات غیرممکن بودن حل، تحت فرضهای داده شده ظاهر می‌شود ."
کار بر روی این مسئله برای یافتن راه حل بر اساس اعداد طبیعی بوده‌است نه تمام اعداد صحیح، اما به سادگی می‌توان دریافت که الگوریتم درهر دو حالت می‌تواند برای دیگری به کار رود. اگر مشخص شود یکی از الگوریتم‌ها با اعداد طبیعی قابل حل است، این می‌تواند برای مشخص کردن اینکه آیا معادله n مجهولی
با قراردادن الگوریتم مفروض در 2 n معادله دارای پاسخ صحیح است
برعکس، یک الگوریتم برای تست کردن حل پذیری، با اعداد صحیح دلخواه، با به کار گیری الگوریتم مفروض برای معادله حاصل از جایگزینی هر مجهول در معادله داده شده به وسیله مجموع مربعات چهار مجهول جدیدمی تواند برای اینکه معادله داده شده با اعداد طبیعی حل پذیر است استفاده شود. این کار بر اساس قضیه چهار مجذور لاگرانژ است تا نشان دهد که تمام اعداد طبیعی می‌توانند به صورت مجموع چهار مجذور نوشته شود.
مجموعه‌های دیوفانتی
مجموعه‌هایی از اعداد طبیعی، دوتایی‌های طبیعی یا حتی تایی‌های طبیعی، که تعریف دیوفانتی دارند به عنوان مجموعه‌های دیوفانتی شناخته می‌شوند. تعاریف دیوفانتی می‌توانند به وسیله دستگاه معادلات و همین‌طور تک معادله‌ها ارائه شوند، زیرا سیستم زیر:
هم ارز است با این معادله:
مجموعه‌های شمارای بازگشتی می‌توانند بدین گونه توصیف شوند که برای هر کدام از آن‌ها الگوریتمی وجود دارد، که هنگامی که عددی از اعداد داده شده به عنوان ورودی قرار گیرد این الگوریتم بعد از مدتی می‌ایستد. اما زمانی که از اعداد غیر عضو در این مجموعه به عنوان ورودی قرار بگیرد به سمت بی‌نهایت میل می‌کند. این همان گسترش یافته نظریه محاسبه پذیری است (که به عنوان نظریه بازگشت نیز شناخته می‌شود) که توضیح دقیقی بر درک مفهوم محاسبه پذیری الگوریتم ارائه می‌کند، بدین سان ایجاد مفهوم بازگشتی غیرقابل شمارش و بی‌نهایت، مشکل است. واضح است که مجموعه‌های دیوفانتی، بازگشتی و قابل شمارش‌اند. این مسئله به این دلیل است که می‌توان تمام چند تایی‌های ممکن از مجهولات را در یک دنباله مرتب کرده و سپس برای هر یک از مقادیر داده شده از پارامترها، یکی پس از دیگری این چند تایی‌ها را امتحان کرد تا ببینیم آیا پاسخ معادله هستند یا خیر. غیرقابل حل بودن مسئله دهم هیلبرت نتیجه شگفت‌انگیز این واقعیت است که عکس این مسئله صحیح است یعنی:
هر مجموعه بازگشتی قابل شمارش دیوفانتی است.
این نتیجه به نام تئوری ماتیاسویچ (به این دلیل که با ارائه یک مرحله این اثبات را کامل کرد) و نظریهMRDP (از ابتدای نامهای افراد زیر گرفته شده است: یوری ماتیاسویچ، جولیا رابینسون، مارتین دیویس، و هیلاری پاتنام) شناخته شده‌است. از این جهت که مجموعه بازگشتی قابل شمارش نیست، غیرقابل حل بودن مسئله دهم هیلبرت به آسانی نتیجه می‌شود. این را بدین گونه می‌توان گفت که در اینجا یک چندجمله‌ای با ضرایب صحیح
به گونه‌ای که مجموعه مقادیر برای معادله
که دارای جوابهایی در اعداد طبیعی است، غیرقابل محاسبه است؛ بنابراین نه تنها یک الگوریتم کلی برای آزمایش قابل حل بودن معادلات دیافونتی وجود ندارد، بلکه برای این خانواده از معادلات هیچ الگوریتمی وجود ندارد.
تاریخچه
سال
رخدادها
۱۹۴۴
امیل لئون پست اعلام کرد که مسئله دهم هیلبرت "به دنبال اثبات غیر قابل حل پذیری است."
۱۹۴۹
مارتین دیویس از روش کارت گودل برای کاربرد قضیه باقی‌مانده چینی به عنوان روش کد گذاری برای به دست آوردن شکل عادی آن برای مجموعه‌های بازگشتی قابل شمارش استفاده کرده‌است:
جایی که چندجمله‌ای با ضرایب صحیح است.
به‌طور کلی این تنها یک کمیت سنج کلی کران دار است که می‌تواند در تعریف دیوفانتی بگنجد.
با استفاده از یک اثبات آسان و غیر پیچیده، وی توضیح داد که در اینجا یک مجموعه دیوفانتی وجود دارد که متمم آن دیوفانتی نیست. چرا که مجموعه‌های بازگشتی قابل شمارش نیز با متمم گیری بسته نمی‌شوند.
۱۹۵۰
جولیا رابینسون، بی‌خبر از کار دیویس، و با درک اهمیت موضوع تابع نمایی، تلاش نمود تا ثابت کند که EXP، مجموعه‌ای از سه تایی‌های (a,b،c) است که برای هر a=b c دیوفانتی ست.
تلاش‌های وی به نظریه‌اش منجر شد (که بعدها به نام J.R معروف شد):
یک مجموعه دیوفانتی D از دوتایی (a,b) وجود دارد، به‌طوری که:
و برای هر ،
به‌طوری‌که
او با استفاده از خواص معادله پل، اثبات کرد که J.R نشان می‌دهد EXP یک دیوفانتی است. در نهایت وی نشان داد که اگر EXP یک دیوفانتی باشد پس ضرایب دو جمله‌ای، فاکتوریل و اول هستند.
۱۹۵۹
دیویس و پاتنام باهمکاری یکدیگر بر روی مجموعه‌های دیوفانتی نمایی کار کردند: مجموعه‌هایی که با معادلات دیوفانتی قابل توضیح هستند دربرخی نماها ممکن است مجهول باشند. استفاده از فرم نرمال دیویس به همراه روش‌های رابینسون، و با ادعای این گمان که در اینجا تصاعدهای حسابی طولانی و تصادفی، شامل اعداد اول هستند، اثبات کردند که هر مجموعه بازگشتی قابل شمارش یک دیوفانتی نمایی است و نشان می‌دهد که مسئله دهم هیلبرت غیرقابل حل است.
۱۹۶۰
رابینسون نشان داد که چگونه جلوی حدس و گمان‌های اثبات نشده را درباره تصاعدهای حسابی اعداد اول بگیریم و به شکل قابل توجهی اثبات J.R. را ساده کرد که به عنوان یک فرایند اساسی برای پیشرفت‌های آینده قرار گرفت، هر چند شک و تردیدهای زیادی در درست بودن آن وجود دارد.
۱۹۶۱–۱۹۶۹
دیویس و پانتام گزاره‌های متفاوتی را که دلالت بر J.R. یافتند. یوری ماتیاسویچ برخی مسائل ساده از مسئله دهم هیلبرت را منتشر کرد. رابینسون نشان داد که وجود مجموعه دیوفانتی نا متناهی در اعداد اول می‌تواند برای بنای نظریه J.R. کافی باشد.
۱۹۷۰
ماتیاسویچ دستگاهی از ده معادله درجه اول و دوم که یک تعریف دیوفانتی از مجموعه زوجهای (a,b) را طوری عرضه می‌کند که
وقتی که برابر با nامین عدد فیبوناتچی باشد را عرضه داشت.
این قضیه را J.R. اثبات کرد و اثبات اینکه تمام مجموعه‌های بازگشتی، شمارا دیوفانتی هستند را تکمیل نموده و نشان داد که مسئله دهم هیلبرت قابل حل نیست.
کاربردها
قضیه ماتیاسویچ/ ام آردی پی دو مفهوم را به یکدیگر مرتبط می‌کند- یکی نظریه قابل شمارش بودن و دیگری نظریه اعداد- و دارای چند نتیجه شگفت‌انگیز است. شاید یکی از شگفت‌انگیزترین این نتایج وجود یک معادله دیوفانتی کلی باشد:
یعنی وجود به‌طوری‌که، برای هر مجموعه دیوفانتی داده شده وجود دارد یک به‌طوری که
درستی این روش به سادگی قابل مشاهده است چرا که ماشین‌های تورینگ قابلیت اجرای هر الگوریتمی را دارند. هیلاری پاتنام نشان داد که برای هر مجموعه دیوفانتی S از اعداد صحیح مثبت، چندجمله‌ای
وجود دارد به‌طوری‌که درآن S دقیقا شامل اعداد مثبتی هستند که در بین مقادیر q بردشان مانند
همه اعداد طبیعی است. این موضوع می‌تواند در ادامه دیده شود: اگر
نشان دهنده تعریف دیوفانتی S باشد، پس کافی است که
بنا بر این به عنوان مثال، یک چندجمله‌ای وجود دارد که قسمت مثبت بردش دقیقا اعداد اول باشند. (از طرفی هیچ چندجمله‌ای نمی‌تواند فقط اعداد اول را بدهد)
کاربرد دیگر آن درباره چیزی است که منطق دانان از آن‌ها به نام گزاره‌های یاد می‌کنند، یا برخی مواقع از آن به عنوان گزاره‌های گلدباخ نام برده می‌شود. اینها شبیه حدس گلدباخ هستند، اظهار می‌دارد که تمام اعداد طبیعی دارای خاصیتی هستند که قابلیت بررسی الگوریتیمیک برای هر عدد خاص را دارا هستند. قضیه ماتیاسویچ/MRDP نشان می‌دهد که این گونه گزاره‌ها هم ارز این حکم هستند که برخی ازمعادلات دیوفانتی هیچ گونه پاسخی در اعداد طبیعی ندارند.
تعدادی از مسائل مهم به این شکل هستند: قضیه آخر فرما، فرضیه ریمان، و قضیه چهار رنگ؛ بعلاوه ادعای اینکه برخی از سیستم‌های قراردادی مثل حساب پئانو یا ZFC می‌توانند به شکل جملات توضیح داده شوند. ایده این است که نشان داده شود کارت گودل در کد گذاری اثباتها به وسیله اعداد طبیعی به روشی است که مشخصه‌اش قابلیت بررسی پذیری یک اثبات به وسیله عددی که به نمایندگی از آن اثبات آمده می‌باشد.
جملات دارای خاصیت ویژه‌ای هستند از این قرار که اگر آن‌ها نادرست باشند، آن حقیقت درهر نوع سیستم صوری معمولی قابل اثبات است.
این موضوع به این دلیل است که اشتباه مقادیر در مثال نقض را بتوان به سادگی بررسی کرد. پس اگر یک جمله طوری باشد که نه خودش و نه نقیضش در یکی از این سیستم‌ها قابل اثبات باشد پس جمله باید درست باشد.
همچنین نتیجه قضیه ماتیاسویچ/MRDP، یک شکل خاص از قضیه ناتمامیت گودل است:
فرض کنید
هیچ جوابی در اعداد طبیعی نداشته باشد. پس یک عدد n 0 وجود دارد که در خروجی A نیست و در حقیقت معادله
هیچ جوابی در اعداد طبیعی ندارد.
برای اینکه ببینیم این قضیه درست است، کافی است توجه کنیم که اگر هیچ عددی مثل n 0 نباشد، می‌توان به صورت الگوریتمی عضویت عدد در این مجموعه نا شمارا را هم‌زمان با اجرای الگوریتمA بررسی کنیم تا ببینیم آیا در خروجی هست؟ و هم‌زمان تمام k-تایی‌های ممکن از اعداد طبیعی برای یافتن جواب معادله را برررسی کنیم:
ما می‌توانیم یک الگوریتم A را با هر سیستم طبیعی صوری (مثل حساب پئانو یا ZFC) با فرض تولید سیستماتیک نتایج از اصول موضوعه مرتبط کنیم و سپس عدد n را هرگاه یک جمله‌ای به فرم زیر تولید گردد بدست آوریم:
پس این قضیه به ما می‌گوید که در این سیستم ممکن است حتی عبارتی با این شکل اگر چه غلط اما ثابت شده باشد؛ یا عبارتی درست همچنان بدون اثبات باقی‌مانده باشد.
نتایج بیشتر
ما می‌توانیم از درجه یک مجموعه دیوفانتی به عنوان کوچکترین درجه چندجمله‌ای یی که معادله معرف مجموعه است، صحبت کنیم. به‌طور مشابه ما می‌توانیم بعد یک چنین مجموعه‌ای را به صورت کمترین تعداد از مجهولات در تعریف معادله مطرح کنیم. به دلیل وجود یک معادله کلی دیوفانتی، مشخص است که کرانه‌های بالایی مطلقی برای هر دوی این معادلات وجود دارد و علاقه بسیاری نیز برای مشخص کردن این کرانه‌ها وجود دارد.
در دهه ۱۹۲۰ ثورالف اسکالم نشان داد که هر معادله دیوفانتی با یک معادله از درجه چهار یا کمتر هم ارز است. تلاش وی این بود که مجهولات جدیدی را با استفاده از معادلات طوری معرفی کند که آن‌ها با مربع یکی از مجهولات یا حاصلضرب دو مجهول برابر باشند. تکرار این فرایند در یک دستگاه معادلات درجه دوم نتیجه داد، و سپس یک معادله درجه چهارم، با جمع مربع‌ها بدست آمد. پس هر مجموعه دیوفانتی معمولا از درجه چهار یا کمتر است. البته هنوز مشخص نیست که آیا این بهترین نتیجه ممکن است یا خیر.
جولیا رابینسون و یوری ماتیاسویچ نشان دادند که هر مجموعه دیوفانتی یک بعد دارد که بیشتر از ۱۳ نیست. بعدها ماتیاسویچ نشان داد که ۹ مجهول هم کافی است. هرچند این نتیجه نیز ممکن است بهترین نتیجه نباشد، اما هنوز پیشرفت دیگری در این زمینه وجود ندارد هنوز هیچ الگوریتمی برای تست کردن معادلات دیوفانتی با ۹ مجهول یا کمتر در دامنه اعداد وجود ندارد. در مورد پاسخ‌های گویای صحیح (مثل آنچه که هیلبرت خود آن را مطرح کرد) روش چهار مربع نشان می‌دهد که هیج الگوریتمی برای معادلات با تعداد کوچکتر مساوی ۳۶ مجهول وجود ندارد. اما زی وی سان نشان داد که این مسئله برای اعداد صحیح حتی برای معادلات با تعداد کوچکتر مساوی ۱۱ مجهول نیز قابل حل نیستند.
مارتین دیویس معادلات الگوریتمی‌ای که شامل تعدادی از پاسخ‌های معادله دیوفانتی بودند را بررسی کرد. مسئله دهم هیلبرت به دنبال این است که آن عدد ۰ است یا نه. فرض کنید و فرض کنید یک زیر مجموعه ناتهی خاص از باشد. دیویس ثابت کرد که هیچ الگورتیمی برای آزمایش یک معادله دیوفانتی داده شده جهت مشخص کردن اینکه آیا تعداد پاسخ‌های آن عضو مجموعه هستند یا خیر وجود ندارد. بنا بر این هیچ الگوریتمی وجود ندارد تا نشان دهد تعداد پاسخ‌های این معادله دیوفانتی متناهی، فرد، مربع کامل، عدد اول و یالله هست یا نه.
تعمیم‌های مسئله دهم هیلبرت
هرچند هیلبرت این مسئله را برای اعداد گویای صحیح مطرح کرد، اما مطرح کردن آن برای خیلی از حلقه‌ها می‌تواند مفید باشد (مخصوصا برای هر حلقه‌ای که اعضای آن قابل فهرست کردن باشد). مثال‌های واضح آن حلقه‌های اعداد صحیح در میدانهای اعداد جبری و همچنین اعداد گویا هستند. یک الگوریتیم مانند چیزی که وی به دنبال آن بود می‌تواند برای پوشاندن دامنه‌های دیگر بسط داده شود. به عنوان مثال معادله زیر:
وقتی که یک چندجمله‌ای با درجه d باشد، در اعداد گویای غیر منفی قابل حل است اگر و تنها اگر: در اعداد طبیعی قابل حل باشد. (اگر کسی یک الگوریتیم داشته باشد تا بتواند قابل حل بودن در اعداد گویای غیر منفی را نشان دهد، به راحتی می‌تواند قابل حل بودن آن را در اعداد گویا نیز نشان دهد) به هر حال دانستن اینکه چنین الگوریتیمی که هیلبرت آرزویش را داشت وجود ندارد، چیزی پیرامون زمینه‌های دیگر نمی‌گوید.
کارهای بسیاری پیرامون مسئله دهم هیلبرت برای حلقه‌های صحیح از میدانهای اعداد جبری انجام گرفته‌است. بر اساس کارهای اولیه جان دنف و لئونارد لیپسچیتز و با استفاده از نظریه class field هارولد ان شاپیرو و الکساندر شاپینتاخ توانستند اثبات کنند:
مسئله دهم هیلبرت برای حلقه‌های صحیح از هر میدان اعداد جبری که گروه گالوا روی اعداد گویا آبلی‌اند غیرقابل حل‌اند.
شلاپینتاخ و ثاناسیس فیداس (مستقل از یکدیگر) به نتیجه یکسانی در زمینه میدانهای اعداد جبری دست یافتند و آن پذیرفتن یک زوج مزدوج مختلط تعبیه شده‌است.
مسئله حلقه اعداد صحیح از میدانهای اعداد جبری به غیر از نتایجی که در بالا مطرح شد هنوز برای پاسخ گویی باز است. همچنین با وجود تلاشهای بسیار، مسئله معادلات در اعداد گویا نیز هنوز برای پاسخ گویی باز است. باری مازور حدس زده که برای هر متغیری در اعداد گویا، بستار توپولوژیکی روی اعداد حقیقی از مجموعه جواب‌ها، دارای مولفه‌های زیاد اما متناهی است.
این حدس می‌گوید که اعداد صحیح روی اعداد گویا دیوفانتی نیستند و همچنین اگر این حدس درست باشد، پاسخ منفی به مسئله دهم هیلبرت مستلزم رویکردی متفاوت برای حلقه‌های دیگر است.
پی‌نوشت‌ها