موضوع مقاله: کاهش‌پذیری تورینگ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کاهش‌پذیری تورینگ | مقدمه: عمل کاهش تورینگ در نظریهٔ زبان‌ها و ماشین‌ها، فرایندی است که در آن یک مسئله مانند به مسئله‌ای مانند تبدیل می‌شود به‌طوری‌که حل مسئلهٔ منجر به حل مسئلهٔ خواهد شد. | ## بخش 1: کاهش‌پذیری تورینگ | فرایند کاهش را به صورت تئوری با تابعی تعریف می‌کنند که در ورودی مسئله‌ای در قالب مسئلهٔ را می‌خواند و در خروجی مسئله‌ای در قالب مسئلهٔ را تولید می‌کند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب حل شود، پاسخ آن پاسخی بر مسئلهٔ نیز خواهد بود. لازم به ذکر است که عمل کاهش تنها وجود تابع معادل‌سازی یک مسئله با مسئله دیگر را تضمین می‌کند و حرفی از حل‌پذیری، تشخیص‌پذیری و تصمیم‌پذیری هر یک از مسائل درگیر به‌طور مستقل به میان نمی‌آورد. در واقع کاهش مسئلهٔ به مسئلهٔ ، وابستگی دو مسئله به یکدیگر را بیان می‌کند و نشان‌دهندهٔ آن است که سختی حل مسئلهٔ به میزان سختی حل مسئلهٔ است. تاریخچه اولین بار وجود ارتباط میان حل مسائل با عنوان حل وابسته یا محاسبهٔ نسبی توسط آلن تورینگ در سال ۱۹۳۹ از دیدگاه ماشین‌های اوراکل مطرح شد. پس از آن استیون کول کلینی در سال‌های ۱۹۴۳ و ۱۹۵۲ مفهومی مشابه را از دیدگاه توابع بازگشتی مطرح کرد. در سال ۱۹۴۴ امیل لئون پست عنوان «کاهش تورینگ» را برای تعریف این مفهوم به کار گرفت. کاربرد ما در عمل، به‌طور معمول روزانه بارها و بارها از فرایند کاهش استفاده می‌کنیم. | ## بخش 2: کاهش‌پذیری تورینگ | در همین فرایند چند مرحله‌ای معمول، مسئلهٔ سفر به مسئلهٔ خرید بلیت، مسئلهٔ خرید بلیت به مسئلهٔ تهیهٔ پول و مسئلهٔ تهیهٔ پول به مسئلهٔ کار کردن کاهش یافت. این دسته‌بندی، مسائل مختلف را از نظر تشخیص‌پذیری، تصمیم‌پذیری، زمان و حافظه به هم مربوط می‌کند و تلاش‌های دنیای علم را در راستای حل مسائل سامان می‌بخشد. تعریف دیدگاه الگوریتمی از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ تعریف می‌شود به‌طوری‌که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ است. کاهش‌پذیری به به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ و تابع هدف آن مجموعهٔ باشد و به صورت زیر نمایش داده می‌شود: دیدگاه ماشین‌های اوراکل از دیدگاه ماشین‌های اوراکل، هرگاه مسئله‌ای مانند به مسئله‌ای مانند کاهش‌پذیر باشد، به ازای هر الگوریتمی برای می‌توان الگوریتمی برای تعبیه کرد به این صورت که به ازای هر فراخوانی اوراکل در ماشین اوراکل الگوریتم مربوط به را قرار داد. از آنجایی که ممکن است ماشین اوراکل چندین بار ماشین اوراکل را فراخوانی کند، زمان و حافظهٔ مورد نیاز این الگوریتم ممکن است به صورت چشم‌گیری از زمان و حافظهٔ مورد نیاز ماشین اوراکل و یا ماشین‌های اوراکل دیگر مربوط به بیشتر باشد. به همین علت تبدیل مسئلهٔ به مسئلهٔ از نظر زمانی و حافظه مورد توجه و اهمیت قرار گرفته‌است. هم‌ارزی تورینگ اگر و هر دو به یکدیگر کاهش‌پذیر باشند، و را هم‌ارز تورینگ می‌نامند. به این صورت تمامی مسائل به کلاس‌های هم‌ارزی تورینگ تقسیم خواهد شد که عضویت در هر یک از این کلاس‌ها درجه تورینگ مسائل را نشان می‌دهد. | ## بخش 3: کاهش‌پذیری تورینگ | در یک مجموعه از مسائل مانند مجموعهٔ ، اگر هر مسئله مانند در مجموعهٔ ، به مسئلهٔ مشخصی مانند کاهش‌پذیر باشد، را تورینگ-سخت برای مجموعهٔ می‌نامند. همچنین در صورتی که خود عضوی از مجموعهٔ باشد، آن را تورینگ-تمام برای مجموعهٔ تعریف می‌کنند. مثال و مسائل معروف عمل کاهش را در اثبات تصمیم‌ناپذیری یکی از مسائل معروف ریاضی شرح می‌دهیم. مجموعهٔ را مجموعه جفت ماشین تورینگ‌هایی تعریف می‌کنیم که تولیدکننده یک زبان مساوی هستند. زیرا در صورتی که تصمیم‌پذیر باشد، با توجه به این که به این مسئله کاهش یافته، نیز تصمیم‌پذیر خواهد شد که یک تناقض را نتیجه می‌دهد. برای کاهش مسئلهٔ به مسئلهٔ ، خاصیت تهی بودن یک زبان را می‌توان با خاصیت تساوی آن زبان با یک زبان تهی معادل کرد. بنابراین در صورتی که ورودی مسئلهٔ را با ماشین یک زبان تهی به مسئلهٔ بدهیم، پاسخ آن برای نیز پاسخی صحیح است. به صورت مشابه تصمیم‌ناپذیری مسائلی همچون مجموعهٔ ماشین‌های زبان‌های منظم، ماشین‌های با نوار محدود و زبان تهی، مسئلهٔ معروف و دیگر مسائل ثابت شده‌است. | ## جمع‌بندی | در عمل می‌توان این قانون را به این صورت تفهیم کرد که تبدیل مسئلهٔ به با اعمال متوالی توابع تبدیل به و تبدیل به بر روی مسئله‌ای در قالب صورت می‌پذیرد.