محاسبه‌پذیری

ایده اساسی در محاسبه‌پذیری این است که یک مسئله که یک task است که محاسبه‌پذیری ان را می‌توان بررسی کرد. دو نوع اصلی از مسایل وجود دارد:

مسئلهٔ تصمیم پذیری، یک مجموعه S را معین می‌کند که ممکن است مجموعه‌ای از رشته‌ها، اعداد طبیعی، یا اشیاء دیگری باشد که از مجموعه بزرگتری مانند U امده‌اند باشد. یک مثال خاص از مسئله تصمیم‌گیری این است که ایا یک عنصر u دلخواه از U در S است. به عنوان مثال، اکر U مجموعهٔ اعداد طبیعی و S مجموعهٔ اعداد اول باشد، مسئلهٔ تصمیم‌گیری به تصمیم‌گیری اول بودن تبدیل می‌شود.

مسئلهٔ تابع، شامل یک تابع f از مجموعه U به V است. مجموعه به عنوان یک نمونه از مسئله محاسبهٔ مقدار تابع f برای u داده شده از مجموعه U است. به عنوان مثال، اگر U و V مجموعهٔ تمام رشته‌های دودویی متناهی باشند و f یک رشته را گرفته و معکوس آن را به عنوان خروجی برگرداند آنگاه f(۱۰۱۰) = ۱۰۱۰.

انواع دیگر مسایل شامل مسایل جستجو و مسایل بهینه‌سازی هستند.

یکی از اهداف نظریه محاسبه‌پذیری تعیین این است که کدام مسایل، یا کلاسی از مسئله‌ها، قابل حل در کدام یک از مدل‌های محاسبه‌پذیری هستند.

یک مدل محاسبه‌پذیری توصیفی رسمی از نوع خاصی از روند محاسباتی است. توضیحات اغلب به شکل یک ماشین انتزاعی است که برای در دسترس قرار دادن مسئله است. مدل‌های عمومی محاسبه‌پذیری معادل با ماشین تورینگ عبارتند از (نگاه کنید به:تز چرچ-تورینگ):

محاسبات شامل یک عبارت لامبدا اولیه (یا دو عبارت برای جدا کردن تابع و ورودی آن) به علاوه یک دنباله متناهی از ترم‌های لامبدا، که هر کدام توسط اعمال یک قانون کاهشی بتا از ترم قبل استنباط می‌شوند.

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

محاسبات شامل یک تابع μ-بازگشتی است، یعنی، یک مقدار ورودی و دنباله‌ای از توابع بازگشتی ظاهر شدن در تعریف دنباله ظاهر می ضوند به همراه ورودی و خروجی آنها؛ بنابراین، اگر در دنباله تعریف تابع بازگشتی (f(x توابع (g(x و (h(x,y ظاهر شوند، انگاه ممکن است ترم‌های 'g(5)=۷' یا 'H (3،۲) = ۱۰' ظاهر شوند. هر ورودی در این دنباله، یا خروجی یک تابع اولیه است یا با استفاده از مطالب بالا بوسیلهٔ ترکیب بازگشت‌های اولیه یا μ-بازگشت بدست می‌آید. به عنوان مثال اگر ((f(x)=h(x,g(x، آنگاه برای وجود داشتن ترم 'F (5) = ۳'، عباراتی مانند " g(5) = ۶" و "H (3،۶) = ۳ "باید رخ دهد. محاسبات تنها زمانی متوقف می‌شود که ترم نهایی ارزش تابع بازگشتی اعمال شده در ورودی را اخذ کند.

با توجه به الگوریتم مارکوف، که با استفاده از قوانین شبه گرامری روی رشته‌هایی از نمادها اعمال می‌شود.

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

تقریباً شبیه به ماشین با وضعیت‌های متناهی است، با این تفاوت که ورودی در "نوار" اجرایی داده می‌شود که ماشین تورینگ می‌تواند از روی ان بخواند، روی ان بنویسد، یا توسط "head" خود به جلو و عقب حرکت کند. نوار می‌تواند به اندازه دلخواه رشد کند. ماشین تورینگ توانایی انجام محاسبات پیچیده که ممکن است مدت زمان اجرای نامعلوم داشته باشد، را دارد. این مدل است که احتمالاً مهم‌ترین مدل محاسبه در علوم کامپیوتر است، چرا که محاسبه‌پذیری را در غیاب محدودیت منابع از پیش تعریف شده شبیه‌سازی می‌کند.

در اینجا ممکن است بیش از یک نوار وجود داشته باشد. و حتی ممکن است چندین head برای یک نوار وجود داشته باشد. با کمال تعجب، هر محاسبه‌ای که می‌تواند توسط این نوع ماشین انجام شود می‌تواند توسط یک ماشین تورینگ معمولی نیز انجام شود، هر چند که حالت دوم ممکن است آهسته‌تر باشد یا به یک منطقه بزرگتر از نوار نیاز داشته باشد.

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

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

یکی دیگر از مدل‌های سادهٔ محاسبه‌پذیری است، اگر چه دنباله پردازش آن منحصر به فرد نیست. می‌توان آن را به عنوان در نظر گرفتن مسیرهای چندگانه محاسبه به‌طور هم‌زمان از طریق یک تعداد متناهی از وضعیت‌ها تفسیر کرد. با این حال می‌توان ثابت کرد که هر NFA قابل تقابل به یک DFA معادل است.

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

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

دانشمندان کامپیوتر هر زبان که بتواند توسط یک ماشین پشته‌ای پذیرش شود را یک زبان مستقل از متن می‌نامند که می‌توان برای ان یک گرامر مستقل از متن معرفی کرد. . زبان مجموعهٔ رشته‌هایی که شامل تعداد مساوی از حروف 'a' و 'b' است که نشان دادیم یک زبان منظم نیست رامی توان با یک ماشین پشته‌ای پذیرش کرد. همچنین، به‌طور کلی، یک ماشین پشته‌ای می‌تواند درست مثل یک ماشین متناهی رفتار کند، پس بوسیلهٔ ان می‌توان هر زبان منظم را پذیرش کرد. در نتیجه این مدل محاسبه به شدت قوی تر از ماشین متناهی است. با این حال، هنوز زبان‌هایی وجود دارند که توسط ماشین پشته‌ای قابل تصمیم‌گیری نیستند. یک مثال از چنین زبانی مجموعهٔ اعداد اول است. مشابه زبان‌های منظم لم تزریق برای زبان‌های مستقل از متن نیز وجود دارد.

ماشین تورینگ می‌تواند هر زبان مستقل از متن را پذیرش کند به علاوه می‌تواند زبان‌هایی که توسط ماشین پشته‌ای قطعی قابل تصمیم‌گیری نیستند، مانند زبان اعداد اول، را نیز پذیرش کند. این مدل یک مدل به شدت قوی محاسبه‌پذیری می‌باشد. از آنجا که ماشین تورینگ توانایی «بازگشت» در نوار ورودی خود را دارد، برای یک ماشین تورینگ این احتمال وجود دارد که برای مدت زمان طولانی اجرا شود در حالی که این عمل در هیچ‌یک از مدل‌های محاسبه‌پذیری دیگری که قبلاً توضیح دادیم امکان‌پذیر نمی‌باشد. ممکن است که یک ماشین تورینگ ساخته شود که برای برخی از ورودی‌ها هیچ وقت متوقف نشود. می‌گوییم یک ماشین تورینگ یک زبان را می‌پذیرد اگر به ازای تمام رشته‌های ورودی ان زبان ماشین متوقف شود. زبانی که به صورت فوق قابل تصمیم‌گیری است یک زبان بازگشتی نامیده می‌شود. می‌توان ماشین تورینگ‌هایی تعریف کرد که برای هر ورودی در زبان یک جواب تولید کند و سپس متوقف شود، اما ممکن است برای رشته‌های ورودی که در زبان نیستند ماشین متوقف نشود. چنین ماشین‌های تورینگی می‌توانند به ما بگویند که یک رشته داده شده در زبان هست، اما بر اساس رفتار آن ممکن است هرگز نفهمیم که یک رشته داده شده در یک زبان نیست، چرا که در بعضی حالت‌ها ممکن است ماشین هرگز متوقف نشود. زبانی که توسط چنین ماشین تورینگی پذیرش می‌شود زبان شمارش پذیر بازگشتی نامیده می‌شود. ماشین تورینگ، که یک مدل بسیار قدرتمند اتوماتا است. تلاش برای اصلاح تعریف ماشین تورینگ برای تولید یک ماشین قدرتمند تر به طرز شگفت‌آوری با شکست روبرو شده‌است. به عنوان مثال، اضافه کردن تعداد دلخواهی از نوارها به ماشین تورینگ، می‌توان ماشین بدست آمده را توسط یک ماشین تورینگ تک نواره شبیه‌سازی کرد. در نتیجه این مدل قوی تر نیست. در واقع، نتیجهٔ قضیه Church-Turing این است که هیچ مدل منطقی محاسبه‌پذیری که بتواند زبانی را که توسط یک ماشین تورینگ قابل تصمیم‌گیری نیست را پذیرش کند.

سؤالی که مطرح می‌شود این است که:ایا زبانی وجود دارد که «بازگشتی شمارش پذیر» باشد، ولی بازگشتی نباشد؟ و به علاوه، زبانی وجود دارد که حتی «بازگشتی شمارش پذیر» نباشد؟

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

طبق قضیه Church-Turing هیچ مدل منطقی محاسبه‌پذیری که بتواند زبانی را که توسط یک ماشین تورینگ قابل تصمیم‌گیری نیست را پذیرش کند وجود ندارد. دانشمندان کامپیوتر انواع بسیاری از hypercomputers معرفی کرده‌اند که مدل‌های محاسبهٔ فراتر از ماشین تورینگ هستند.

تصور کنید یک ماشین که در آن هر مرحله از محاسبات نیاز به نیمی از زمان مرحله قبل را دارد. اگر ما به ۱ واحد زمان برای مرحله اول نیاز داشته باشیم، انگاه زمان مورد نیاز برای اجرای ماشین به صورت: ... +۱+۱/۲+۱/۴ است. این سری همگرا به ۲ واحد زمان است، که به این معنی است که این ماشین تورینگ می‌تواند بی‌نهایت بار در ۲ واحد زمان اجرا شود. این ماشین می‌تواند مشکل تصمیم‌گیری توقف را به‌طور مستقیم با شبیه‌سازی سؤال به صورت بالا حل کند؛ که می‌توان ان را به کار با هر سری همگرا گسترش داد. اگر فرض کنیم این سری همگرا به یک مقدار n است آنگاه ماشین تورینگ عملیات نامتناهی را در n واحد زمان انجام می‌دهد.

به اصطلاح ماشین‌های اوراکلی دسترسی به نوعی "وحی" دارند که ارائه دهنده راه حلی برای برخی مسایل تصمیم ناپذیر است. برای مثال، ماشین تورینگ ممکن است یک "halting oracle" داشته باشد، که بلافاصله پاسخ دهد، ایا یک ماشین تورینگ برای یک ورودی داده شده متوقف می‌شود. این نوع ماشین یک موضوع اصلی در مطالعه نظریهٔ بازگشت است.

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