Reduktionen

Mann muss eine totale und funktionale Relation bilden.

Wenn $L_1\le L_2$, dann:
$L_1$ (semi) entschidbar $\Leftarrow$ $L_2$ (semi) entschidbar
$L_1$ nicht entschidbar $\Rightarrow$ $L_2$ nicht entschidbar

siehe
Turing-Reduktionen
reduziere Wortproblem auf Halteproblem
Halteproblem
Wortproblem