موضوع مقاله: محاسبه‌پذیری | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # محاسبه‌پذیری | مقدمه: محاسبه‌پذیری توانایی حل یک مسئله به روشی مؤثر است؛ که یک موضوع کلیدی در زمینه نظریه محاسبه پذیری در منطق ریاضی و نظریه محاسبات در علوم کامپیوتر است. | ## بخش 1: محاسبه‌پذیری | گسترده‌ترین مدل‌های مورد مطالعه از محاسبات توابع تورینگ-محاسبه پذیر، μ-بازگشتی و حساب لامبدا هستند، که تمامی آن‌ها دارای قدرت محاسباتی معادل هستند. از انواع دیگر مطالعه محاسبه پذیری، همچنین: مفاهیم محاسبه‌پذیری ضعیف تر از ماشین‌های تورینگ که در نظریه اتوماتا مطالعه می‌شود و مفاهیم محاسبه‌پذیری قوی تر از ماشین تورینگ که در زمینه hypercomputation مطالعه می‌شود را می‌توان نام برد. مسایل ایده اساسی در محاسبه‌پذیری این است که یک مسئله که یک task است که محاسبه‌پذیری ان را می‌توان بررسی کرد. دو نوع اصلی از مسایل وجود دارد: مسئلهٔ تصمیم پذیری، یک مجموعه S را معین می‌کند که ممکن است مجموعه‌ای از رشته‌ها، اعداد طبیعی، یا اشیاء دیگری باشد که از مجموعه بزرگتری مانند U امده‌اند باشد. به عنوان مثال، اکر U مجموعهٔ اعداد طبیعی و S مجموعهٔ اعداد اول باشد، مسئلهٔ تصمیم‌گیری به تصمیم‌گیری اول بودن تبدیل می‌شود. مجموعه به عنوان یک نمونه از مسئله محاسبهٔ مقدار تابع f برای u داده شده از مجموعه U است. به عنوان مثال، اگر U و V مجموعهٔ تمام رشته‌های دودویی متناهی باشند و f یک رشته را گرفته و معکوس آن را به عنوان خروجی برگرداند آنگاه f(۱۰۱۰) = ۱۰۱۰. یکی از اهداف نظریه محاسبه‌پذیری تعیین این است که کدام مسایل، یا کلاسی از مسئله‌ها، قابل حل در کدام یک از مدل‌های محاسبه‌پذیری هستند. مدل‌های رسمی محاسبه‌پذیری یک مدل محاسبه‌پذیری توصیفی رسمی از نوع خاصی از روند محاسباتی است. مدل‌های عمومی محاسبه‌پذیری معادل با ماشین تورینگ عبارتند از (نگاه کنید به:تز چرچ-تورینگ): حساب لامبدا (Lambda calculus) محاسبات شامل یک عبارت لامبدا اولیه (یا دو عبارت برای جدا کردن تابع و ورودی آن) به علاوه یک دنباله متناهی از ترم‌های لامبدا، که هر کدام توسط اعمال یک قانون کاهشی بتا از ترم قبل استنباط می‌شوند. منطق ترکیبی (Combinatory logic) مفهومی است که شباهت‌های بسیاری به حساب لامبدا دارد، ولی تفاوت‌های مهمی نیز وجود دارد (به عنوان مثال ترکیب نقطه ثابت Y در منطق ترکیبی دارای فرم نرمال است در حالی که در حساب لامبدا اینطور نیست). منطق ترکیبی با جاه طلبی‌های بزرگ توسعه داده شده است: درک ماهیت پارادوکس‌ها، ساخت پایه‌های اقتصادی تر (از نظر مفهوم) برای ریاضیات، از بین بردن مفهوم متغیرها. هر ورودی در این دنباله، یا خروجی یک تابع اولیه است یا با استفاده از مطالب بالا بوسیلهٔ ترکیب بازگشت‌های اولیه یا μ-بازگشت بدست می‌آید. به عنوان مثال اگر f(x)=h(x,g(x، آنگاه برای وجود داشتن ترم 'F (5) = ۳'، عباراتی مانند " g(5) = ۶" و "H (3،۶) = ۳ "باید رخ دهد. محاسبات تنها زمانی متوقف می‌شود که ترم نهایی ارزش تابع بازگشتی اعمال شده در ورودی را اخذ کند. در بسیاری از آنها، هر ثبت نام می‌تواند تعدادی عدد طبیعی (با اندازه نامحدود) نگه دارد، و دستورالعمل‌ها ساده‌اند (و کم)، به عنوان مثال تنها عمل کاهش (همراه با پرش شرطی) و افزایش (و توقف) وجود دارد. عدم وجود بی‌نهایت (و یا رشد پویا) ذخیرهٔ خارجی (که در ماشین تورینگ وجود دارد) را می‌توان با جایگزینی نقش ان با تکنیک‌های شماره‌گذاری گودل درک کرد:این واقعیت است که هر ثبت نام یک عدد طبیعی دارد که اجازه می‌دهد تا بتواند نمایندهٔ یک شیء پیچیده باشد (به عنوان مثال یک دنباله، یا یک ماتریس) توسط عدد طبیعی بزرگ مناسب - عدم ابهام در هر دو حالت به نمایندگی گرفتن و تفسیر کردن را می‌توان با پایه‌های نظریه اعدادی این تکنیک‌ها ایجاد کرد. ماشین تورینگ تقریباً شبیه به ماشین با وضعیت‌های متناهی است، با این تفاوت که ورودی در "نوار" اجرایی داده می‌شود که ماشین تورینگ می‌تواند از روی ان بخواند، روی ان بنویسد، یا توسط "head" خود به جلو و عقب حرکت کند. ماشین تورینگ توانایی انجام محاسبات پیچیده که ممکن است مدت زمان اجرای نامعلوم داشته باشد، را دارد. با کمال تعجب، هر محاسبه‌ای که می‌تواند توسط این نوع ماشین انجام شود می‌تواند توسط یک ماشین تورینگ معمولی نیز انجام شود، هر چند که حالت دوم ممکن است آهسته‌تر باشد یا به یک منطقه بزرگتر از نوار نیاز داشته باشد. P مانند ماشین‌های تورینگ، "P از یک نوار نامتناهی (بدون دسترسی تصادفی) و یک مجموعه از دستورالعمل‌ها استفاده می‌کند. | ## بخش 2: محاسبه‌پذیری | اما این دستورالعمل‌ها بسیار متفاوت هستند، بنابراین، بر خلاف ماشین‌های تورینگ، "P نیازی به نگهداری وضعیت‌های مجزا ندارد، چرا که همه توابع "حافظه مانند" را می‌توان تنها بوسیلهٔ نوار ارائه کرد. علاوه بر این مدل‌های محاسباتی کلی، برخی از مدل‌های محاسباتی ساده برای کارهای خاصی، برنامه‌های محدود، مفید هستند. عبارات منظم، به عنوان مثال، مشخص کردن الگوهای رشته‌ای در بسیاری زمینه‌ها، از دفتر بهره‌وری نرم‌افزار تا زبان‌های برنامه‌نویسی. یک فرمالیسم ریاضی دیگر هم ارز با عبارات منظم، اتوماتای متناهی است که در طراحی مدار و در حل برخی از مسئله‌ها استفاده می‌شود. ماشین‌های پشته‌ای غیر قطعی هستند فرمالیسم‌های دیگری هم ارز با گرامر مستقل از متن هستند. یک راه برای اندازه‌گیری قدرت یک مدل محاسباتی مطالعه کلاس زبان رسمی است که مدل فوق می‌تواند تولید کند. سایر مدل‌های متناهی محاسبه‌پذیری عبارتند از: ماشین متناهی قطعی (DFA) همچنین ماشین با تعداد وضعیت متناهی نامیده می‌شود. چنین ماشینی دارای مجموعه‌ای از وضعیت‌ها و مجموعه‌ای از انتقال‌ها برای وضعیت‌ها است که تحت تأثیر جریان ورودی هستند. جریان ورودی در هر زمان به ماشین یک کاراکتر می‌دهد، و انتقال‌های ممکن برای وضعیت فعلی با کاراکتر ورودی مقایسه می‌شود، و اگر با انتقالی مطابقت داشت دستگاه به یک وضعیت جدید می‌رود. در پایان اگر رشتهٔ ورودی ماشین در حالت پذیرش قرار داشت، تمام رشتهٔ ورودی پذیرش می‌شود. ماشین متناهی غیر قطعی (NFA) یکی دیگر از مدل‌های سادهٔ محاسبه‌پذیری است، اگر چه دنباله پردازش آن منحصر به فرد نیست. می‌توان آن را به عنوان در نظر گرفتن مسیرهای چندگانه محاسبه به‌طور هم‌زمان از طریق یک تعداد متناهی از وضعیت‌ها تفسیر کرد. اتوماتای پشته‌ای شبیه به ماشین حالت محدود، به جز آن که یک پشته اجرایی در دسترس دارد، که می‌تواند اندازه دلخواه رشد کند. وضعیت‌های انتقال مشخص می‌کنند که در هر مرحله یک نمادی به پشته اضافه شود یا نمادی از روی پشته حذف شود. این ماشین با توجه به حافظه نامحدود پشتهٔ آن بسیار قدرتمندتر از DFA است، هر چند در هر زمان تنها عنصر بالای پشته در دسترس است. قدرت اتوماتا قدرت ماشین متناهی دانشمندان کامپیوتر هر زبان که بتواند توسط یک ماشین متناهی پذیرش شود را یک زبان منظم می‌نامند. بخاطر محدودیتی که روی تعداد وضعیت‌های یک ماشین متناهی داریم که باید متناهی باشند، متوجه می‌شویم که برای پیدا کردن یک زبان غیر منظم باید یک زبان بیابیم که برای ساخت ان به تعداد نامتناهی وضعیت نیاز باشد. یک مثال از چنین زبانی، مجموعه‌ای از تمام رشته‌های شامل حروف 'a' و 'b' که شامل تعداد مساوی از حرف 'a' و 'b' است؛ که می‌توان بوسیلهٔ لم تزریق برای زبان‌های منظم این ادعا را ثابت کرد. لم تزریق نشان می‌دهد که کلاس‌های گسترده‌ای از زبان‌ها توسط ماشین‌های متناهی قابل تشخیص نیستند. قدرت ماشین پشته‌ای دانشمندان کامپیوتر هر زبان که بتواند توسط یک ماشین پشته‌ای پذیرش شود را یک زبان مستقل از متن می‌نامند که می‌توان برای ان یک گرامر مستقل از متن معرفی کرد. زبان مجموعهٔ رشته‌هایی که شامل تعداد مساوی از حروف 'a' و 'b' است که نشان دادیم یک زبان منظم نیست رامی توان با یک ماشین پشته‌ای پذیرش کرد. | ## بخش 3: محاسبه‌پذیری | همچنین، به‌طور کلی، یک ماشین پشته‌ای می‌تواند درست مثل یک ماشین متناهی رفتار کند، پس بوسیلهٔ ان می‌توان هر زبان منظم را پذیرش کرد. با این حال، هنوز زبان‌هایی وجود دارند که توسط ماشین پشته‌ای قابل تصمیم‌گیری نیستند. قدرت ماشین تورینگ ماشین تورینگ می‌تواند هر زبان مستقل از متن را پذیرش کند به علاوه می‌تواند زبان‌هایی که توسط ماشین پشته‌ای قطعی قابل تصمیم‌گیری نیستند، مانند زبان اعداد اول، را نیز پذیرش کند. از آنجا که ماشین تورینگ توانایی «بازگشت» در نوار ورودی خود را دارد، برای یک ماشین تورینگ این احتمال وجود دارد که برای مدت زمان طولانی اجرا شود در حالی که این عمل در هیچ‌یک از مدل‌های محاسبه‌پذیری دیگری که قبلاً توضیح دادیم امکان‌پذیر نمی‌باشد. ممکن است که یک ماشین تورینگ ساخته شود که برای برخی از ورودی‌ها هیچ وقت متوقف نشود. می‌گوییم یک ماشین تورینگ یک زبان را می‌پذیرد اگر به ازای تمام رشته‌های ورودی ان زبان ماشین متوقف شود. می‌توان ماشین تورینگ‌هایی تعریف کرد که برای هر ورودی در زبان یک جواب تولید کند و سپس متوقف شود، اما ممکن است برای رشته‌های ورودی که در زبان نیستند ماشین متوقف نشود. چنین ماشین‌های تورینگی می‌توانند به ما بگویند که یک رشته داده شده در زبان هست، اما بر اساس رفتار آن ممکن است هرگز نفهمیم که یک رشته داده شده در یک زبان نیست، چرا که در بعضی حالت‌ها ممکن است ماشین هرگز متوقف نشود. زبانی که توسط چنین ماشین تورینگی پذیرش می‌شود زبان شمارش پذیر بازگشتی نامیده می‌شود. تلاش برای اصلاح تعریف ماشین تورینگ برای تولید یک ماشین قدرتمند تر به طرز شگفت‌آوری با شکست روبرو شده است. به عنوان مثال، اضافه کردن تعداد دلخواهی از نوارها به ماشین تورینگ، می‌توان ماشین بدست آمده را توسط یک ماشین تورینگ تک نواره شبیه‌سازی کرد. در واقع، نتیجهٔ قضیه Church-Turing این است که هیچ مدل منطقی محاسبه‌پذیری که بتواند زبانی را که توسط یک ماشین تورینگ قابل تصمیم‌گیری نیست را پذیرش کند. سؤالی که مطرح می‌شود این است که:ایا زبانی وجود دارد که «بازگشتی شمارش پذیر» باشد، ولی بازگشتی نباشد؟ مدل‌های قوی تر محاسبه‌پذیری طبق قضیه Church-Turing هیچ مدل منطقی محاسبه‌پذیری که بتواند زبانی را که توسط یک ماشین تورینگ قابل تصمیم‌گیری نیست را پذیرش کند وجود ندارد. اگر ما به ۱ واحد زمان برای مرحله اول نیاز داشته باشیم، آنگاه زمان مورد نیاز برای اجرای ماشین به صورت: ... این سری همگرا به ۲ واحد زمان است، که به این معنی است که این ماشین تورینگ می‌تواند بی‌نهایت بار در ۲ واحد زمان اجرا شود. این ماشین می‌تواند مشکل تصمیم‌گیری توقف را به‌طور مستقیم با شبیه‌سازی سؤال به صورت بالا حل کند؛ که می‌توان ان را به کار با هر سری همگرا گسترش داد. اگر فرض کنیم این سری همگرا به یک مقدار n است آنگاه ماشین تورینگ عملیات نامتناهی را در n واحد زمان انجام می‌دهد. در حالی که هر یک از آن‌ها می‌تواند مشکل توقف برای یک ماشین تورینگ را حل کند، آن‌ها نمی‌توانند برای خود مسئله توقف را حل کنند. | ## جمع‌بندی | به عنوان مثال، یک ماشین اوراکلی نمی‌تواند این سؤال را که آیا یک ماشین اوراکلی داده شده متوقف می‌شود، پاسخ دهد.