|
Recall the fundamental theorem of mapping reducibility.
Theorem. If B is computable and A ≤ m B then A is computable.
Theorem. If A is uncomputable and A ≤ m B then B is uncomputable.
Earlier, I said that mapping reductions have some advantages over Turing reductions. One advantage is that mapping reductions between partially computable languages in some sense preserve partial computability.
Suppose A and B are two languages.
Theorem. If B is partially computable and A ≤m B, then A is partially computable.
Theorem. If A is not partially computable and A ≤m B, then B is not partially computable.
The proof is left as an exercise.
|