Computability Reductions
Mapping reductions used in computability: any computable function suffices (no polynomial-time bound). These transfer decidability and recognizability — if A ≤m B and B is decidable, so is A; if A ≤m B and A is undecidable, so is B.
ATM ≤m HALTTM
Wrap M so its accept becomes a halt and its reject becomes a loop. Proves HALTTM is undecidable.
HALTTM ≤m ATM
Wrap M so any halting outcome becomes an accept. Shows the two problems are equivalent.
More coming soon
ATM ≤m ETM, ETM ≤m EQTM, and Rice's theorem applications on the way.
Want a specific reduction added? Request it by email at contact@csvisualizer.com.