В теории вычислимости редукция Тьюринга (также известная как редукция Кука ) от проблемы A к проблеме B — это редукция, которая решает A , при условии, что решение B уже известно. Ее можно понимать как алгоритм, который можно было бы использовать для решения A, если бы он имел доступную подпрограмму для решения B. Более формально редукция Тьюринга — это функция, вычисляемая машиной-оракулом с оракулом для B.

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

Связь полноты по Тьюрингу с вычислительной универсальностью

Полнота по Тьюрингу лишь частично соответствует полноте по Тьюрингу в смысле вычислительной универсальности. В частности, машина Тьюринга является универсальной машиной Тьюринга, если ее проблема остановки (набор входных данных, для которых она в конечном итоге останавливается) полна на несколько единиц. Таким образом, необходимое, но недостаточное условие для вычислительной универсальности машины состоит в том, чтобы проблема остановки машины была полной по Тьюрингу для множества X .

Использование

Формально, использование редукции — это функция, которая отправляет каждое натуральное число n в наибольшее натуральное число m, членство которого в множестве B было запрошено сокращением при определении принадлежности n к A.

Ссылки