کاهشپذیری تورینگ
From Wikipedia, the free encyclopedia
عمل کاهش تورینگ در نظریهٔ زبانها و ماشینها، فرایندی است که در آن یک مسئله مانند به مسئلهای مانند تبدیل میشود بهطوریکه حل مسئلهٔ منجر به حل مسئلهٔ خواهد شد. این فرایند را کاهش مسئلهٔ به مسئلهٔ مینامند. فرایند کاهش را به صورت تئوری با تابعی تعریف میکنند که در ورودی مسئلهای در قالب مسئلهٔ را میخواند و در خروجی مسئلهای در قالب مسئلهٔ را تولید میکند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب حل شود، پاسخ آن پاسخی بر مسئلهٔ نیز خواهد بود.
لازم به ذکر است که عمل کاهش تنها وجود تابع معادلسازی یک مسئله با مسئله دیگر را تضمین میکند و حرفی از حلپذیری، تشخیصپذیری و تصمیمپذیری هر یک از مسائل درگیر بهطور مستقل به میان نمیآورد. در واقع کاهش مسئلهٔ به مسئلهٔ ، وابستگی دو مسئله به یکدیگر را بیان میکند و نشاندهندهٔ آن است که سختی حل مسئلهٔ به میزان سختی حل مسئلهٔ است.