در ریاضیات نه یعنی نه، ریاضیات جایی برای اما و اگرهای ما باقی نمیگذارد. اگر به کمک ریاضیات اثبات کردیم که مثلا حل مسالهای امکان پذیر نیست، این به معنیست که هرچقدر هم که علم و تکنولوژی ما پیشرفت کند، در حل آن مساله فرقی نمیکند و آن مساله غیرقابل حل است. مگر اینکه روزی مشخص شود که اثبات ما مشکل داشته است. اجازه دهید با یک مثال به این مساله بپردازیم.
ما در علوم کامپیوتر به دستهای از مسائل، مساله تصمیم یا decision problem میگوییم. این مسائل مسائلی هستند که پاسخ بله یا خیر به ما میدهند. مثلا ما الگوریتمی داریم که به ما میگوید این عدد، عدد اول است؟ بعد الگوریتم به ما میگوید بله یا خیر؟ یعنی شما به کمک الگوریتمی میتوانید بفهمید که این عدد عدد اول است یا نه؟ ما اکنون برای حل این مساله الگوریتمهایی داریم. اما گاهی اوقات، ما نمیتوانیم الگوریتمی پیدا کنیم که حتما به ما جواب دهد. ما به چنین مسائلی که ما نمیتوانیم برای آنها الگوریتم جامعی پیدا کنیم که پاسخ سوال ما را بدهد میگوییم مسائل غیرقابل تصمیم گیری یا undecidable problems.
ما وقتی اثبات کردیم که نمیتوان برای یک مساله چنین الگوریتمی پیدا کرد، آنوقت فرقی نمیکند با چه زبان برنامه نویسی یا کدام برنامه نویس یا کامپیوتر کوانتومی یا سوپر کامپیوتر یا هوش مصنوعی یا هرکس و هرچیز و هر وسیلهی دیگری، نمیتوان برای آن الگوریتمی پیدا کرد. هرکسی هم که ادعا کند در آینده آن مساله حل خواهد شد، یا اطلاعی از این قضیه ندارد یا صرفا دکان داری میکند. من در ادامه میخواهم شما را با یکی از این مسائل آشنا کنم و حتی اثبات آن را نیز در اینجا ارائه کنم. اسم این مساله، مسالهی توقف یا halting problem است.
اولین بار آلونزو چرچ در سال ۱۹۳۶ و آلن تورینگ در سال ۱۹۳۷ به صورت مجزا این مساله را اثبات کردند. مساله میگوید هیچ الگوریتمی وجود ندارد که بتواند بگوید یک الگوریتم دیگر متوقف میشود یا متوقف نمیشود. یعنی ما نمیتوانیم یک الگوریتمی پیدا کنیم که هر الگوریتم دیگری را به آن بدهیم، به ما بگوید که آن الگوریتم پاسخ دارد یا نه؟ پیش از اثبات این مساله، اجازه دهید که یک مثال بزنیم. یک فردی یک روزی به شما میگوید که “من دروغگو هستم”. حالا آیا این حرف او راست است یا دروغ است؟ اگر بگویید راست است پس او دروغگو نیست و اگر بگویید دروغ است، پس او اینجا راست گفته و در این مورد راستگو است.
حالا فرض کنید یک نفر آمده و میگوید من الگوریتمی برای مسالهی توقف پیدا کردهام. میگوییم بسیار خب. ما برای امتحان الگوریتم شما، یک برنامهی دیگر طراحی میکنیم. برنامهی ما یک الگوریتم را میگیرد، اگر آن الگوریتم متوقف شود، برنامهی ما تا بینهایت ادامه پیدا میکند و اگر آن الگوریتم متوقف نشود، الگوریتم ما متوقف میشود. آن شخص میگوید خب چه عالی و چه برنامهی جالبی. آنوقت ما میگوییم خب حالا ما الگوریتمی که تو طراحی کردهای را میخواهیم به عنوان ورودی برنامهی خودمان بدهیم. چون تو گفتی الگوریتم تو برای هر برنامهای میتواند پیشبینی کند که آن متوقف خواهد شد یا نه. اما اینجا ما به همان پارادوکس فرد دروغگو میخوریم.
اگر این الگوریتم بگوید که برنامهی ما متوقف میشود، برنامهی ما تا بینهایت ادامه پیدا میکند و اگر بگوید برنامهی ما متوقف نمیشود، برنامهی ما متوقف میشود و در هر دو حالت به تناقض میرسیم. پس ما اثبات کردیم که مسالهی توقف هیچ جوابی ندارد و این ربطی به توسعهی علم و تکنولوژی نیز ندارد. والسلام.
– ابا اباد