Reduzierbarkeit (Turing)

Eine Sprache $A\subseteq {\mathrm{\Sigma }}^{\ast }$ ist reduzierbar auf eine Sprache $B\subseteq {\mathrm{\Pi }}^{\ast }$ (geschrieben $A\le B$), wenn eine totale, berechenbare Funktion $f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Pi }}^{\ast }$ existiert, sodass für alle $x\in {\mathrm{\Sigma }}^{\ast }$ gilt:

Die Funktion $f$ wird als Reduktion bezeichnet.