کاهش‌پذیری تورینگ
عمل کاهش تورینگ در نظریهٔ زبان‌ها و ماشین‌ها، فرایندی است که در آن یک مسئله مانند به مسئله‌ای مانند تبدیل می‌شود به‌طوری‌که حل مسئلهٔ منجر به حل مسئلهٔ خواهد شد. این فرایند را کاهش مسئلهٔ به مسئلهٔ می‌نامند. فرایند کاهش را به صورت تئوری با تابعی تعریف می‌کنند که در ورودی مسئله‌ای در قالب مسئلهٔ را می‌خواند و در خروجی مسئله‌ای در قالب مسئلهٔ را تولید می‌کند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب حل شود، پاسخ آن پاسخی بر مسئلهٔ نیز خواهد بود.
لازم به ذکر است که عمل کاهش تنها وجود تابع معادل‌سازی یک مسئله با مسئله دیگر را تضمین می‌کند و حرفی از حل‌پذیری، تشخیص‌پذیری و تصمیم‌پذیری هر یک از مسائل درگیر به‌طور مستقل به میان نمی‌آورد. در واقع کاهش مسئلهٔ به مسئلهٔ ، وابستگی دو مسئله به یکدیگر را بیان می‌کند و نشان‌دهندهٔ آن است که سختی حل مسئلهٔ به میزان سختی حل مسئلهٔ است.
تاریخچه[ویرایش]
اولین بار وجود ارتباط میان حل مسائل با عنوان حل وابسته یا محاسبهٔ نسبی توسط آلن تورینگ در سال ۱۹۳۹ از دیدگاه ماشین‌های اوراکل مطرح شد. بعدتر آن را کاهش وابسته یا کاهش نسبی نیز نامیدند. پس از آن استیون کول کلینی در سال‌های ۱۹۴۳ و ۱۹۵۲ مفهومی مشابه را از دیدگاه توابع بازگشتی مطرح کرد. در سال ۱۹۴۴ امیل لئون پست عنوان «کاهش تورینگ» را برای تعریف این مفهوم به کار گرفت. کاهش تورینگ در زمان خطی نیز به نام استیون کوک، کاهش کوک نام گرفت.
کاربرد[ویرایش]
ما در عمل، به‌طور معمول روزانه بارها و بارها از فرایند کاهش استفاده می‌کنیم. برای مثال فرض کنید می‌خواهید از شهری به شهر دیگری سفر کنید. برای این کار نیاز به تهیهٔ بلیت برای سفر دارید. برای تهیهٔ بلیت به تهیهٔ پول نیاز دارید و برای تهیهٔ پول باید کار کنید. در همین فرایند چند مرحله‌ای معمول، مسئلهٔ سفر به مسئلهٔ خرید بلیت، مسئلهٔ خرید بلیت به مسئلهٔ تهیهٔ پول و مسئلهٔ تهیهٔ پول به مسئلهٔ کار کردن کاهش یافت. بنابراین عمل کاهش به صورت کلی بخشی از ساده‌ترین اعمال زندگی روزمرهٔ ما می‌باشد.
کاربرد فنی‌تر عمل کاهش، در مسائل ریاضی می‌باشد. یکی از این کاربردها دسته‌بندی مسائل ریاضی است. این دسته‌بندی، مسائل مختلف را از نظر تشخیص‌پذیری، تصمیم‌پذیری، زمان و حافظه به هم مربوط می‌کند و تلاش‌های دنیای علم را در راستای حل مسائل سامان می‌بخشد.
تعریف[ویرایش]
دیدگاه الگوریتمی[ویرایش]
از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ تعریف می‌شود به‌طوری‌که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ است. این پیاده‌سازی را می‌توان به کمک ماشین‌های اوراکل به انجام رساند.
دیدگاه تئوری و ریاضیاتی[ویرایش]
دو مجموعهٔ و متشکل از اعداد طبیعی را در نظر بگیرید. کاهش‌پذیری به به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ و تابع هدف آن مجموعهٔ باشد و به صورت زیر نمایش داده می‌شود:
دیدگاه ماشین‌های اوراکل[ویرایش]
از دیدگاه ماشین‌های اوراکل، هرگاه مسئله‌ای مانند به مسئله‌ای مانند کاهش‌پذیر باشد، به ازای هر الگوریتمی برای می‌توان الگوریتمی برای تعبیه کرد به این صورت که به ازای هر فراخوانی اوراکل در ماشین اوراکل الگوریتم مربوط به را قرار داد. از آنجایی که ممکن است ماشین اوراکل چندین بار ماشین اوراکل را فراخوانی کند، زمان و حافظهٔ مورد نیاز این الگوریتم ممکن است به صورت چشم‌گیری از زمان و حافظهٔ مورد نیاز ماشین اوراکل و یا ماشین‌های اوراکل دیگر مربوط به بیشتر باشد. به همین علت تبدیل مسئلهٔ به مسئلهٔ از نظر زمانی و حافظه مورد توجه و اهمیت قرار گرفته‌است.
هم‌ارزی تورینگ[ویرایش]
اگر و هر دو به یکدیگر کاهش‌پذیر باشند، و را هم‌ارز تورینگ می‌نامند. به این صورت تمامی مسائل به کلاس‌های هم‌ارزی تورینگ تقسیم خواهد شد که عضویت در هر یک از این کلاس‌ها درجه تورینگ مسائل را نشان می‌دهد.
در یک مجموعه از مسائل مانند مجموعهٔ ، اگر هر مسئله مانند در مجموعهٔ ، به مسئلهٔ مشخصی مانند کاهش‌پذیر باشد، را تورینگ-سخت برای مجموعهٔ می‌نامند. همچنین در صورتی که خود عضوی از مجموعهٔ باشد، آن را تورینگ-تمام برای مجموعهٔ تعریف می‌کنند.
مثال و مسائل معروف[ویرایش]
عمل کاهش را در اثبات تصمیم‌ناپذیری یکی از مسائل معروف ریاضی شرح می‌دهیم. مجموعهٔ را مجموعه جفت ماشین تورینگ‌هایی تعریف می‌کنیم که تولیدکننده یک زبان مساوی هستند. مجموعهٔ را نیز مجموعه ماشین تورینگ‌هایی تعریف می‌کنیم که زبانشان تهی است. می‌دانیم مسئلهٔ تصمیم‌ناپذیر است. با کاهش مسئلهٔ به مسئلهٔ می‌توان نتیجه گرفت که نیز تصمیم‌ناپذیر است. زیرا در صورتی که تصمیم‌پذیر باشد، با توجه به این که به این مسئله کاهش یافته، نیز تصمیم‌پذیر خواهد شد که یک تناقض را نتیجه می‌دهد. برای کاهش مسئلهٔ به مسئلهٔ ، خاصیت تهی بودن یک زبان را می‌توان با خاصیت تساوی آن زبان با یک زبان تهی معادل کرد. بنابراین در صورتی که ورودی مسئلهٔ را با ماشین یک زبان تهی به مسئلهٔ بدهیم، پاسخ آن برای نیز پاسخی صحیح است. بنابراین کاهشی از مسئلهٔ به وجود دارد و هر مسئله از را می‌توان با حل کرد.
به صورت مشابه تصمیم‌ناپذیری مسائلی همچون مجموعهٔ ماشین‌های زبان‌های منظم، ماشین‌های با نوار محدود و زبان تهی، مسئلهٔ معروف و دیگر مسائل ثابت شده‌است.
ویژگی‌ها[ویرایش]
- هر مجموعه به متمم خود کاهش‌پذیر است.
- هر مجموعهٔ بازگشتی به هر مجموعهٔ دیگر کاهش‌پذیر است.
- کاهش‌پذیری تورینگ قابلیت تراگذری دارد. به بیان دیگر اگر و آنگاه داریم . در عمل می‌توان این قانون را به این صورت تفهیم کرد که تبدیل مسئلهٔ به با اعمال متوالی توابع تبدیل به و تبدیل به بر روی مسئله‌ای در قالب صورت می‌پذیرد.
منابع[ویرایش]
- S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland
- Introduction to the Theory of Computation (second edition), by Michael. Sipser, Thomson Course Technology, Boston, 2006
- Turing Computability: Theory and Applications by Robert Soare, Published by ACM 2016