نظریه رایانش‌پذیری

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

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

نظریه شماره پذیری

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

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

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

منطق ترکیبیاتی

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

• کشف طبیعت تناقض‌ها
• اقتصادی تر کردن شالودهٔ ریاضیات
• کاهش نشان گذاری متغیرها

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

یک محاسبه به صورت یک تابع بازگشتی مو است، اگر دنبالهٔ تعریف شدهٔ آن، متغیرهای ورودی و یک دنبالهٔ توابع بازگشتی همراه با ورودی‌ها و خروجی‌های آن مشخص باشند؛ بنابراین اگر در تعریف دنبالهٔ بازگشتی تابع $f(x)$، توابع $g(x)$ و $h(x,y)$ وجود داشته باشند، در نتیجه عباراتی به شکل g(۵)=۷ یا h(۳٬۲)=۱۰ ممکن است ظاهر شوند. در این گونه توابع، اگر آخرین عبارت مقدار تابع بازگشتی ایی که به ورودی‌ها داده شده‌است؛ را بدهد، محاسبات پایان می‌پذیرند. ؛ الگوریتم مارکف یک سیستم رشته‌ای با قابلیت دوباره نویسی، که از قوانین گرامری شکلی برای به کار انداختن رشته‌ها استفاده می‌کند.

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

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

P

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

جستارهای وابسته

• نظریه محاسبات
• نظریه پیچیدگی محاسباتی

منابع

http://en.wikipedia.org/wiki/Theory_of_computation

Introductory Theory of Computer Science, E. V. Krishnamurthy, East-West Press, 1983

http://www-groups.dcs.st-and.ac.uk/history/Mathematicians/Panini.html