Let .
A total Computable function is a reduction from to if for all we have:
We also say that is many-to-one reducible to .
We write
Note that is a Partial Preorder
The following proposition says that is at most as complicated as
(in the computability sense).
Proposition
If and is Computable, then so is .
If and is Computably Enumerable, then so is .