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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

مسایل[ویرایش]

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

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

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

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

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

مدل‌های رسمی محاسبه پذیری[ویرایش]

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

حساب لاندا (Lambda calculus)[ویرایش]

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

منطق ترکیبی (Combinatory logic)[ویرایش]

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

توابع μ-بازگشتی (μ-recursive functions)[ویرایش]

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

سیستم‌های بازنویسی رشته(String rewriting systems)[ویرایش]

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

دستگاه ثبت نام (Register machine)[ویرایش]

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

ماشین تورینگ[ویرایش]

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

ماشین تورینگ چند نواره[ویرایش]

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

P[ویرایش]

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

ماشین متناهی قطعی (DFA)[ویرایش]

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

ماشین متناهی غیر قطعی (NFA)[ویرایش]

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

اتوماتای پشته‌ای[ویرایش]

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

قدرت اتوماتا[ویرایش]

قدرت ماشین متناهی[ویرایش]

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

قدرت ماشین پشته‌ای[ویرایش]

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

قدرت ماشین تورینگ[ویرایش]

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

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

مدل‌های مبتنی بر همزمانی (Concurrency-based models)[ویرایش]

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

مدل‌های قوی تر محاسبه پذیری[ویرایش]

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

Infinite execution[ویرایش]

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

ماشین اوراکلی(Oracle machines)[ویرایش]

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

محدودیت‌های hyper-computation[ویرایش]

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

منابع[ویرایش]

Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Part Two: Computability Theory, Chapters 3–6, pp. 123–222.

Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 3: Computability, pp. 57–70.

S. Barry Cooper (2004). Computability Theory (1st ed.). Chapman & Hall/CRC. ISBN: 978-1-58488-237-4.