تئوری رایانش‌پذیری چیست و به چه مفهومی اشاره دارد؟

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

مسئله دهم هیلبرت جزء فهرست مسائل هیلبرت است که در سال ۱۹۰۰ مطرح شده‌است. صورت این مسئله چنین است، آیا الگوریتمی برای تعیین حل‌پذیری معادلات سیاله با ضرایب عددی گویا و هر تعداد مجهول وجود دارد؟ یعنی فرایندی ابداع شود که بر اساس آن بتوان یک تعداد متناهی از عملگرها را مشخص کرد تا معادله با اعداد صحیح گویا قابل حل باشد. کارهای بسیاری پیرامون مسئله دهم هیلبرت برای حلقه‌های صحیح از میدان‌های اعداد جبری انجام گرفته‌است. بر اساس کارهای اولیه جان دنف و لئونارد لیپسچیتز و با استفاده از نظریه class field هارولد ان شاپیرو و الکساندر شاپینتاخ توانستند اثبات کنند: مسئله دهم هیلبرت برای حلقه‌های صحیح از هر میدان اعداد جبری که گروه گالوا روی اعداد گویا آبلی اند غیرقابل حل‌اند. شلاپینتاخ و ثاناسیس فیداس (مستقل از یکدیگر) به نتیجه یکسانی در زمینه میدان‌های اعداد جبری دست یافتند و آن پذیرفتن یک زوج مزدوج مختلط تعبیه شده‌است. مسئله حلقه اعداد صحیح از میدان‌های اعداد جبری به غیر از نتایجی که در بالا مطرح شد هنوز برای پاسخ گویی باز است. همچنین با وجود تلاش‌های بسیار، مسئله معادلات در اعداد گویا نیز هنوز برای پاسخ گویی باز است. باری مازور حدس زده که برای هر متغیری در اعداد گویا، بستار توپولوژیکی روی اعداد حقیقی از مجموعه جواب‌ها، دارای مؤلفه‌های زیاد اما متناهی است. این حدس می‌گوید که اعداد صحیح روی اعداد گویا دیوفانتی نیستند و همچنین اگر این حدس درست باشد، پاسخ منفی به مسئله دهم هیلبرت مستلزم رویکردی متفاوت برای حلقه‌های دیگر است.

ماشین تورینگ

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

بازگشت/  توابع بازگشتی

بازگشت (Recursion) در علوم رایانه، روشی برای حل یک مسئله است که در آن راه‌حل مسئله به راه‌حل‌هایی در نمونه‌های کوچکتر از همان مساله وابسته است.  به نظر می‌رسد ترجمه «بازگشت» بیشتر مناسب کلمه انگلیسی Return باشد تا کلمه Recursion ؛ به همین دلیل بعضی از اساتید عبارت توابع خوداتکاء را برای نامیدن این‌گونه توابع به کار می‌برند. همچنین از آنجایی که ریشه این کلمه در زبان انگلیسی فعل Recur به معنای اتفاق افتادن مجدد است، ترجمه‌های مناسب دیگر می‌توانند توابع بازوقوع و توابع بازفراخوانی شونده باشند که همگی قطعا بهتر از ترجمه مشهور و ضعیف آن (توابع بازگشتی) می‌باشند. به هر حال، نگرش خوداتکاء یا بازگشتی در علم کامپیوتر یک روش فکر کردن برای حل مسائل است. در واقع خوداتکایی یا بازگشت یکی از ایده‌های اصلی علم کامپیوتر است. حل یک مسئله به روش خوداتکاء/بازگشتی بدین معناست که راه حل بستگی به مدل کوچکتری از صورت مسئله داشته باشد. در ریاضیات کاربردی و به خصوص کامپیوتر، مسائل فراوانی وجود دارد که حل آن‌ها را به سادگی می‌توان به صورت یک الگوریتم بازگشتی نشان داد. یک الگوریتم بازگشتی مانند یک تابع یا یک دنباله بازگشتی تعریف می‌شود فرمان‌های الگوریتم به‌طور مکرر و با پارامترهای مختلف اجرا می‌شوند تا به فرمان بنیادی الگوریتم برسیم. آنگاه تمام مقادیری را که محاسبه آن‌ها انجام نشده‌است را به صورت بازگشتی محاسبه می‌نماییم تا فرمان مورد نظر اجرا شود. یک روش متداول برای آسان‌سازی مسائل این است که آن‌ها را به زیر مسائلی از همان نوع تقسیم بندی کنیم. این روش با نام گویشی کردن شناخته می‌شود. به عنوان یک تکنیک برنامه نویسی کامپیوتر، به این روش تقسیم و غلبه گفته می‌شود. و کلید راه حل تعداد زیادی از مسائل کامپیوتری مهم است و یک بخش اساسی می‌باشد. تمام زبان‌های برنامه‌نویسی که امروز مورد استفاده‌اند تعریفی مستقیم از توابع بازگشتی در خود دارند. وقتی چنین تابعی فراخوانی می‌شود، کامپیوتر(برای اکثر زبان‌هایی که پشته دارند) یا خود کد زبان instanceهای مختلف تابع را (با فراخوانی پشته، هر چند روش‌های دیگر هم مورد استفاده قرار می‌گیرند). برعکس آن همه توابع بازگشتی می‌توانند به کمک پشته به یک تابع غیر بازگشتی تبدیل شوند. اکثر توابع و روش‌هایی که می‌توانند بوسیله کامپیوتر ارزشیابی شوند بدون استفاده از غیر بازگشتی کردن قابل بازگشتی شدن هستند.

بازگشت به نظریه رایانش‌پذیری

قدرت بازگشت قطعاً در این نهفته ‌است که دسته‌ای نامتناهی از اشیا را بوسیله یک عبارت متناهی تعریف می‌کند. به معنای دیگر یک عدد نامتناهی در محاسبات می‌تواند بوسیله یک برنامه متناهی بازگشتی تعریف شود حتی اگر این برنامه هیچ تکرار واضحی نداشته باشد.

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

نظریه شماره پذیری، با این سؤال که آیا یک مسئله قابل حل بر روی یک کامپیوتر هست یا نه، سر و کار دارد. مسئله halting یکی از مهم‌ترین نتایج در نظریه شماره پذیری است. این مسئله به آسانی قابل قاعده سازی و به سختی با استفاده از ماشین تورینگ قابل حل است! بخش عمده‌ای از نظریه شماره پذیری، بر نتیجه مسئله  halting، استوار است. نظریه  شماره پذیری، با یک شاخه از منطق ریاضی به نام نظریه  بازگشت، در ارتباط تنگاتنگ است. بسیاری از ریاضی دانان و نظریه پردازان شمارش پذیری، که درباره  نظریه  بازگشت به مطالعه می‌پردازند، این نظریه را در آخر به نظریه  شماره پذیری ارجاع می‌دهند.

نظریه پیچیدگی

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

منطق ترکیبی

مفهومی است که شباهت‌های زیادی به حساب لامبدا دارد. اما تفاوت‌های عمده‌ای نیز دارند. منطق ترکیبیاتی با تلاش‌های بسیار پیشرفت زیادی در زمینه‌های زیر داشته‌است:

کشف طبیعت تناقض‌ها

اقتصادی تر کردن شالوده ریاضیات

کاهش نشان گذاری متغیرها

توابع بازگشتی مو

ماشین رجیستر (Register Machine)

یک کامپیوتر ایده‌آل تئوریک است! متغیرهای بیشتری وجود دارد. در بسیاری از آن‌ها، هر رجیستر می‌تواند یک عدد طبیعی با سایز نامحدود، را نگهداری کند، دستور العمل‌ها ساده هستند؛ برای مثال فقط کاستن پله‌ای و نمو وجود دارد. کمبود ذخیره خارجی که در ماشین‌های تورینگ دیده می‌شود، می‌تواند با جایگذاری نقشش با استفاده از روش‌های عددی Godel درک شود. این حقیقت که هر رجیستر قابلیت نگهداری یک عدد طبیعی را دارد، امکان نمایش یک چیز پیچیده‌تر (مثلاً یک دنباله یا یک ماتریس)، را فراهم می‌سازد. همانند ماشین‌های تورینگ، این روش نیز از نشان‌های بی‌نهایت (بدون دسترسی تصادفی) استفاده می‌کند. هم چنین تعداد دستورالعمل‌ها کمتر است. اما این دستورالعل‌ها بسیار متفاوت هستند، بنابراین بر خلاف ماشین تورینگ، P" نیازی به نگه داشتن یک حالت مشخص نیست، چرا که تمام عملیات حافظه گونه فقط با استفاده از نوار تأمین می‌شود. به جای دوباره‌نویسی نشان جاری، می‌تواند یک نمو حسابی پیمانه‌ای را انجام دهد.