Reducción de Turing
- Natural & Formal Sciences -
Mathematics & Logic Dictionary
Definición
Una relación entre problemas de decisión (conjuntos) A y B donde A es reducible de Turing a B si existe una máquina de Turing que decide la pertenencia a A dada una oráculo para B; equivalentemente, A es computable relativamente a B.