(۰۶ دى ۱۳۹۰ ۰۱:۰۱ ب.ظ)NoOne نوشته شده توسط:  سلام
بچه‌ها کسی میتونه بحث تصمیم پذیری،توقف پذیری و کاهش پذیری رو واسه من توضیح بده فرقشونو.کلا قضیه چیه؟

البته اینجور مسائل توی کتابای مربوط به نظریه محاسبات مثل کتاب سیپسر (که ترجمش هم هست) و کتاب Papadimitriou کامل توضیح داده می شه.

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

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

توقف پذیری همون مسئله Halting Problem هست که می گه: آیا ماشین تورینگی وجود داره که به ازای یک ماشین تورینگ و یک رشته ورودی، در زمان متناهی بتونه بگه که ماشین تورینگ ورودی، در زمان متناهی بر روی رشته ورودی متوقف می شه (یعنی یا قبولش می کنه یا ردش می کنه.) یا نه؟

کاهش پذیری یا Reducibility هم در واقع تبدیل یک مسئله در زمانی متناهی به یک مسئله مشخص دیگر هست. مثلا مسئله بررسی تهی بودن یک زبان رو می شه کاهش داد به Halting Problem. یعنی یک مسئله رو تبدیل کنیم به یه حالت خاص از یک مسئله دیگه. برای مثال اونوقت اگر اون حالت خاص هر حالتی از تصمیم پذیری رو نداشته باشه، مسئله اول هم نداره. یعنی اگر دومی تصمیم ناپذیر باشه، اولی هم تصمیم ناپذیره. کاربردش هم اینه که شما از یه سری مسائل اثبات شده استفاده می کنید تا برای مسائل جدیدتر اثبات بیارید. ضمنا کاهش پذیری حالات مختلفی داره و فقط برای بررسی تصمیم پذیری استفاده نمی شه. برای بررسی پیچیدگی زمان و حتی فضای حل یک مسئله هم استفاده می شه.

البته باز هم میگم، تعاریف بالا به شدت عامیانه و غیر دقیق هستند. برای اطلاعات بیشتر و دقیقتر به کتابایی که گفتم مراجعه کنید. سرچ توی ویکی پدیا هم اکیدا توصیه می شه.