Redução (teoria da recursão)
De Wikipedia, a enciclopédia encyclopedia
Na Teoria da computação, muitos tipos de reduções são estudadas. A motivação para tal, é a seguinte: dado os conjuntos de números naturais A e B, é possível efetivamente converter um método de decisão para B em um método de decisão para A? Se a resposta para essa questão for positiva, então pode se dizer que A é redutível a B.
O estudo de noções de redutibilidade é motivado pelo estudo da decisão de problemas. Para noção de muitos problemas de redutibilidade, se algum conjunto não-computável é redutível a um conjunto A, então A deve ser não computável. Isto nos dá uma técnica muito poderosa para provar que muitos conjuntos de problemas são não-computáveis.