«تصمیم پذیری و مسئله دهم هیلبرت»

یکی از عمیق ترین مباحث علوم کامپیوتر که همیشه برای من جالب بوده است بحث "تصمیم پذیری" و "محاسبه پذیری" و مسائلی از این دست بوده است.

یکی از مسائل مهم در ریاضی که با مبحث تصمیم پذیری ارتباط خود را آشکار می کند، مسئله دهم هیلبرت است.

هیلبرت در 1900 لیستی از 23 مسئله که از نظر او مهم بود را مطرح کرد که همگی در آن زمان حل نشده بودند. تلاش برای حل این مسائل (مثل تلاش برای حل مسائل مهم دیگر در تاریخ ریاضیات) از عوامل پیشرفت ریاضی در قرن بیستم بود.

تا کنون برخی از این مسائل حل شده، بر روی برخی از آن ها حرف و حدیث هایی باقیست و 4 تای آن ها هنوز حل نشده اند که حدس ریمان هم از جمله ی آن هاست.

در ارتباط با مسئله دهم (که حل شده است) نکته ای را خواستم بگویم:

صورت مسئله دهم به طور خلاصه و با حذف جزئیات تکنیکی اینگونه است: "اگر معادله دیوفانتینی با تعداد متغیر های دلخواه و ضرایب ... داده شده باشد، آیا امکان ایجاد فرآیندی کلی وجود دارد که طی مراحلی متناهی، امکان حل پذیر بودن آن را تعیین کند؟"

جواب منفیست.

اثبات آن توسط افراد زیر طی 21 سال به طول انجامید:

Martin Davis
Yuri Matiyasevich
Hilary Putnam
Julia Robinson

و در نهایت این Matyiasevich بود که در 1970 به جمعبندی رسید و آن را تکمیل کرد و اکنون به این مسئله قضیه Matiyasevich یا قضیه MRDP هم می گویند.

در حقیقت وقتی در مورد تصمیم پذیری مسئله ای می خواهیم کار کنیم، ابتدا ظاهر مسئله را به گونه ای تغییر می دهیم و ساده می کنیم که مسئله تبدیل به مسئله "بله" یا "خیر" شود. آنگاه اگر الگوریتمی برای حل آن وجود نداشته باشد می گوییم مسئله تصمیم ناپذیر است. دقت کنید که مسئله ما جواب بله یا خیر به یک مصداق خاص از یک مسئله عام نیست. مثلاً در همین مسئله دهم هیلبرت به دنبال ساخت الگوریتم برای یک معادله خاص نیستیم، بلکه به دنبال الگوریتم کلی هستیم.

در آینده اگر مجالی داد در مورد بحث عمیق تصمیم پذیری در ریاضی و کامپیوتر بیشتر صحبت می کنیم.

#MojeeNC
@harmoniclib

شما هم با هشتگ اختصاصی خودتون نویسنده ی کانال « اخبار و کتاب های ریاضی » بشید. اینجوری اعضای کانال بهتر می توانند پیگر مطالب شما باشند. حتی می توانید مطالبتون را به صورت سریالی بفرستید.
بدین منظور بهم پیام بدید👇👇👇
@meisami_mah
و با تعیین یه هشتگ ، مطالب جذابتون را بفرستید.

وبینار گروه ترکیبیات و محاسبه، پاییز 1399
@harmoniclib

فراخوان دوره پسادکتری-جایزه مریم میرزاخانی https://math.ipm.ac.ir/Postdoc
@harmoniclib

فرمول های مشتق و انتگرال
@harmoniclib
برای دیدن کامل عکس بر روی آن ضربه بزنید.

جادوی ریاضیات در معماری
@harmoniclib

نه اثبات از نامتناهی بودن اعداد اول
برای همه بفرستید👈👈👈
@harmoniclib

این ۴۰ ثانیه را حتماً ببینید.
روی من که خیلی تأثیر گذاشت.
@harmoniclib

مقایسه اندازه ی چند قمر از سیارات ( مریخ و زحل و مشتری) با اندازه ی زمین.
@harmoniclib

کارگاه حل مسئله جبر خطی
https://t.iss.one/joinchat/BHVqPkVqHFlUnC8bfKFA4Q

وقتی دو ستاره ی نوترونی برخورد می کنند این اتفاق می افتد.
به نظر شما چگونه می توان چنین پدیده ای را مدلسازی ریاضی کرد؟!
@harmoniclib

جواب ارسالی
سلام
راجع‌به پست آخرتون که در رابطه با برخورد ستاره هاست می‌خواستم بگم:
دو ستاره نوترونی در صورت برخورد با‌هم به یک ستاره‌ی نوترونی بزرگتر یا به سیاهچاله تبدیل می‌شن ولی در فیلم سوپرنوا اتفاق افتاد و اون دو تا ستاره‌ی اولیه باید از نوع کوتوله سفید باشن.
@harmoniclib

دوستان عزیز اگر کسی دسترسی به فیلم این سخنرانی و یا لینک فایل ضبط شده آن دارد برای من ارسال نماید👇
@meisami_mah

نقشه ی آلودگی نوری ایران
@harmoniclib

«حدس abc و موچیزوکی»

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

اثبات موچیزوکی برای حدس abc از جمله این موارد است. ابتدا سعی می کنم توضیحاتی مقدماتی و مختصر در مورد حدس abc ارائه کنم، سپس به حواشی اثبات موچیزوکی و وضعیت روز مسئله می پردازم.

این حدس را ابتدا Joseph Oesterlé (1988) و David Masser (1985) در نظریه اعداد مطرح کردند. حدس abc در حال حاضر اهمیت زیادی دارد، چرا که از نتایج آن حدس ها و قضایای مهم دیگری می باشد، لذا به نظر می رسد اهمیت بنیادی تری حتی نسبت به حدس فرما داشته باشد، چرا که جالب است بدانید از پیامد های حل این حدس، حدس آخر فرما است که البته به دلیل حل شدن آن توسط وایلز به آن قضیه آخر فرما می گویند. از جمله پیامد های این حدس موارد زیر می باشند:

-حدس Beal
-قضیه Faltings
-قضیه آخر فرما
-حدس فرما-کاتالان
-قضیه Roth
-قضیه Tijdeman

گولدفلد (1996) حدس abc را به عنوان "مهم ترین مسئله حل نشده آنالیز دیوفانتینی" توصیف کرد.

توصیف فشرده و کلی از حدس abc:

علت نامگذاری حدس abc به خاطر وجود سه عدد صحیح مثبت a و b و c در صورت آن بوده که نسبت به هم اولند و در a + b = c صدق کنند. در صورتی که چنین اعدادی را یافتیم، ضرب عوامل اول متمایز آن سه عدد را d می نامیم، این حدس ادعا می کند که d اساساً خیلی کوچکتر از c نیست. به بیان دیگر، اگر a و b از توان های بزرگی از عوامل اول تشکیل شده باشند، آنگاه c اغلب بر توان های بزرگی از اعداد اول بخش پذیر نیست.

ممکن است از توصیف فوق که سعی شده حداکثر سادگی را داشته باشد سردرگم شده باشید. سعی می کنم صورت مسئله را به صورت دقیق تر توضیح دهم:

در حقیقت به d رادیکال abc می گوییم. با چند مثال رادیکال اعداد صحیح را می توان به راحتی فهمید:

rad(18)=2*3
rad(9)=3
rad(100)=2*5
...

یعنی عوامل آن عدد با توان 1 را در هم ضرب می کند و به عنوان خروجی تحویل می دهد. حال شکل دقیق تری از حدس abc به این شکل در خواهد آمد:

برای هر عدد حقیقی دلخواهی چون ε، تنها تعداد متناهی از سه تایی های دو به دو متباین (نسبت به هم اول) a و b و c وجود دارند به گونه ای که a+b=c باشد و داشته باشیم:

c>rad(abc)^(1+ε)

در آگوست 2012، Shinichi Mochizuki ادعا کرد که اثباتی برای حدس Szpiro دارد. از آنجا که با تغییر حدس Szpiro مشخص می شود که این حدس با حدس abc معادل است، پس اگر اثبات او درست باشد عملاً حدس abc هم اثبات شده است. بررسی این که چرا از آن زمان تا کنون سر اثبات موچیزوکی مناقشه است و این که در مجموع اثبات بسیار حجیم موچیزوکی از چه نظریاتی صحبت می کند بحث مفصل و عمیقی می طلبد که در این مقال نگنجد. در آینده به گوشه های قابل فهمی از اثبات آن و حواشی و وضعیت روز مسئله می پردازم.

#MojeeNC
@harmoniclib