Reducción: A reduce a B si se puede computar A utilizando el programa B a través de un programa f que utilice B y sea computable.

La computabilidad es cerrada por el complemento: A es computable si solo si A complemento es computable.
A es computable si solo si A es computablemente enumerable y A complemento es computablemente enumerable.