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