کاهش‌پذیری تورینگ
عمل کاهش تورینگ در نظریهٔ زبان‌ها و ماشین‌ها، فرایندی است که در آن یک مسئله مانند formula_1 به مسئله‌ای مانند formula_2 تبدیل می‌شود به‌طوری‌که حل مسئلهٔ formula_2 منجر به حل مسئلهٔ formula_1 خواهد شد. این فرایند را کاهش مسئلهٔ formula_1 به مسئلهٔ formula_2 می‌نامند. فرایند کاهش را به صورت تئوری با تابعی تعریف می‌کنند که در ورودی مسئله‌ای در قالب مسئلهٔ formula_1 را می‌خواند و در خروجی مسئله‌ای در قالب مسئلهٔ formula_2 را تولید می‌کند. در این صورت مسائل ورودی و خروجی تابع معادل شده و اگر مسئله حاصل در قالب formula_2 حل شود، پاسخ آن پاسخی بر مسئلهٔ formula_1 نیز خواهد بود.
لازم به ذکر است که عمل کاهش تنها وجود تابع معادل‌سازی یک مسئله با مسئله دیگر را تضمین می‌کند و حرفی از حل‌پذیری، تشخیص‌پذیری و تصمیم‌پذیری هر یک از مسائل درگیر به‌طور مستقل به میان نمی‌آورد. در واقع کاهش مسئلهٔ formula_1 به مسئلهٔ formula_2، وابستگی دو مسئله به یکدیگر را بیان می‌کند و نشان‌دهندهٔ آن است که سختی حل مسئلهٔ formula_1 به میزان سختی حل مسئلهٔ formula_2 است.
اولین بار وجود ارتباط میان حل مسائل با عنوان "حل وابسته" یا "محاسبهٔ نسبی" توسط آلن تورینگ در سال ۱۹۳۹ از دیدگاه ماشین‌های اوراکل مطرح شد. بعدتر آن را "کاهش وابسته" یا "کاهش نسبی" نیز نامیدند. پس از آن استیون کول کلینی در سال‌های ۱۹۴۳ و ۱۹۵۲ مفهومی مشابه را از دیدگاه توابع بازگشتی مطرح کرد. در سال ۱۹۴۴ امیل لئون پست عنوان «کاهش تورینگ» را برای تعریف این مفهوم به کار گرفت. کاهش تورینگ در زمان خطی نیز به نام استیون کوک، "کاهش کوک" نام گرفت.
ما در عمل، به‌طور معمول روزانه بارها و بارها از فرایند کاهش استفاده می‌کنیم. برای مثال فرض کنید می‌خواهید از شهری به شهر دیگری سفر کنید. برای این کار نیاز به تهیهٔ بلیت برای سفر دارید. برای تهیهٔ بلیت به تهیهٔ پول نیاز دارید و برای تهیهٔ پول باید کار کنید. در همین فرایند چند مرحله‌ای معمول، مسئلهٔ سفر به مسئلهٔ خرید بلیت، مسئلهٔ خرید بلیت به مسئلهٔ تهیهٔ پول و مسئلهٔ تهیهٔ پول به مسئلهٔ کار کردن کاهش یافت. بنابراین عمل کاهش به صورت کلی بخشی از ساده‌ترین اعمال زندگی روزمرهٔ ما می‌باشد.
کاربرد فنی‌تر عمل کاهش، در مسائل ریاضی می‌باشد. یکی از این کاربردها دسته‌بندی مسائل ریاضی است. این دسته‌بندی، مسائل مختلف را از نظر تشخیص‌پذیری، تصمیم‌پذیری، زمان و حافظه به هم مربوط می‌کند و تلاش‌های دنیای علم را در راستای حل مسائل سامان می‌بخشد.
از دیدگاه الگوریتمی، شرح عمل کاهش به این صورت است که الگوریتمی برای حل مسئلهٔ formula_1 تعریف می‌شود به‌طوری‌که در آن بخش اصلی حل مسئله بر دوش زیرروالی است که خود شامل الگوریتم حل مسئلهٔ formula_2 است. این پیاده‌سازی را می‌توان به کمک ماشین‌های اوراکل به انجام رساند. دو مجموعهٔ formula_1 و formula_2 متشکل از اعداد طبیعی را در نظر بگیرید. کاهش‌پذیری formula_1 به formula_2 به معنای وجود تابعی است که دامنهٔ آن مجموعهٔ formula_1 و تابع هدف آن مجموعهٔ formula_2 باشد و به صورت زیر نمایش داده می‌شود:
formula_23
از دیدگاه ماشین‌های اوراکل، هرگاه مسئله‌ای مانند formula_1 به مسئله‌ای مانند formula_2 کاهش‌پذیر باشد، به ازای هر الگوریتمی برای formula_2 می‌توان الگوریتمی برای formula_1 تعبیه کرد به این صورت که به ازای هر فراخوانی اوراکل formula_2 در ماشین اوراکل formula_1 الگوریتم مربوط به formula_2 را قرار داد. از آنجایی که ممکن است ماشین اوراکل formula_1 چندین بار ماشین اوراکل formula_2 را فراخوانی کند، زمان و حافظهٔ مورد نیاز این الگوریتم ممکن است به صورت چشم‌گیری از زمان و حافظهٔ مورد نیاز ماشین اوراکل formula_2 و یا ماشین‌های اوراکل دیگر مربوط به formula_1 بیشتر باشد. به همین علت تبدیل مسئلهٔ formula_1 به مسئلهٔ formula_2 از نظر زمانی و حافظه مورد توجه و اهمیت قرار گرفته‌است.
اگر formula_1 و formula_2 هر دو به یکدیگر کاهش‌پذیر باشند، formula_1 و formula_2 را هم‌ارز تورینگ می‌نامند. به این صورت تمامی مسائل به کلاس‌های هم‌ارزی تورینگ تقسیم خواهد شد که عضویت در هر یک از این کلاس‌ها درجه تورینگ مسائل را نشان می‌دهد.
در یک مجموعه از مسائل مانند مجموعهٔ formula_41، اگر هر مسئله مانند formula_42 در مجموعهٔ formula_41، به مسئلهٔ مشخصی مانند formula_44 کاهش‌پذیر باشد، formula_44 را تورینگ-سخت برای مجموعهٔ formula_41 می‌نامند. همچنین در صورتی که formula_44 خود عضوی از مجموعهٔ formula_41 باشد، آن را تورینگ-تمام برای مجموعهٔ formula_41 تعریف می‌کنند.
عمل کاهش را در اثبات تصمیم‌ناپذیری یکی از مسائل معروف ریاضی شرح می‌دهیم. مجموعهٔ formula_50 را مجموعه جفت ماشین تورینگ‌هایی تعریف می‌کنیم که تولیدکننده یک زبان مساوی هستند. مجموعهٔ formula_51 را نیز مجموعه ماشین تورینگ‌هایی تعریف می‌کنیم که زبانشان تهی است. می‌دانیم مسئلهٔ formula_51 تصمیم‌ناپذیر است. با کاهش مسئلهٔ formula_51 به مسئلهٔ formula_50 می‌توان نتیجه گرفت که formula_50 نیز تصمیم‌ناپذیر است. زیرا در صورتی که تصمیم‌پذیر باشد، با توجه به این که formula_51 به این مسئله کاهش یافته، formula_51 نیز تصمیم‌پذیر خواهد شد که یک تناقض را نتیجه می‌دهد. برای کاهش مسئلهٔ formula_51 به مسئلهٔ formula_50، خاصیت تهی بودن یک زبان را می‌توان با خاصیت تساوی آن زبان با یک زبان تهی معادل کرد. بنابراین در صورتی که ورودی مسئلهٔ formula_51 را با ماشین یک زبان تهی به مسئلهٔ formula_50 بدهیم، پاسخ آن برای formula_51 نیز پاسخی صحیح است. بنابراین کاهشی از مسئلهٔ formula_51 به formula_50 وجود دارد و هر مسئله از formula_51 را می‌توان با formula_50 حل کرد.
به صورت مشابه تصمیم‌ناپذیری مسائلی همچون مجموعهٔ ماشین‌های زبان‌های منظم، ماشین‌های با نوار محدود و زبان تهی، مسئلهٔ معروف formula_67 و دیگر مسائل ثابت شده‌است.