Computation

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.

Request more
Missing something? Get in touch and we'll add it.