redução de Turing

Na Teoria da Computação, a redução de Turing de um problema A para um problema B, nomeado após Alan Turing, é uma redução que resolve A, assumindo que B já é conhecido(Rogers 1967, Soare 1987). Esta pode ser entendida como um algoritmo que pode ser usado para resolver A se este for for válido como uma sub-rotina que resolve B. De uma maneira mais formal, a redução de Turing é uma função computável por uma máquina Turing com um oráculo para B. A redução de turing pode ser aplicada tanto para problemas de decisão quanto para problemas problemas de função. Se uma redução de Turing de A para B existe, então todo algoritmo que resolve B pode ser usado para produzir um algoritmo que resolve A, inserindo o algoritmo que resolve B em cada lugar onde a máquina de Turing com um oráculo, ao computar A, consulta o oráculo de B. Entretanto, já que a máquina Turing com oráculo pode fazer um grande número de consultas ao oráculo, o algoritmo resultante pode requerer mais tempo do que o normal do que qualquer M ou máquina Turing com oráculo e pode necessitar de tanto espaço quanto os dois juntos. A primeira definição formal de uma computação relativa, depois chamada de redutibilidade relativa, foi dada por Alan Turing em 1939 na definição da máquina de Turing com oráculo. Depois, em 1943 e 1952, Stephen Kleene definiu um conceito equivalente sobre a definição de funções recursivas. Em 1944 Emil Post usou a definição de "Redução de Turing" para se referir ao conceito.