Редукция Тьюринга

В теории вычислимости редукция Тьюринга (также известная как редукция Кука ) от проблемы A к проблеме B - это редукция, которая решает A, при условии, что решение B уже известно. Ее можно понимать как алгоритм, который можно было бы использовать для решения A, если бы он имел доступную подпрограмму для решения B. Более формально редукция Тьюринга - это функция, вычисляемая машиной-оракулом с оракулом для B. Первое формальное определение относительной вычислимости, которое тогда называлось относительной сводимостью, было дано Аланом Тьюрингом в 1939 году в терминах машин-оракулов. Позже, в 1943 и 1952 годах, Стивен Клини определил эквивалентное понятие в терминах рекурсивных функций. В 1944 году Эмиль Пост использовал термин «сводимость Тьюринга» для обозначения этой концепции.