Введение

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

Отношение Тьюринговой полноты к вычислительной универсальности

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

Пример

Пусть обозначает множество входных значений, для которых машина Тьюринга с индексом *e* останавливается. Тогда множества и являются Тьюринг-эквивалентными (здесь обозначает эффективную функцию спаривания). Сокращение, показывающее , может быть построено, используя тот факт, что . Для заданной пары , новый индекс может быть построен с помощью теоремы smn таким образом, чтобы программа, закодированная индексом , игнорировала свой вход и просто имитировала вычисление машины с индексом *e* на входе *n*. В частности, машина с индексом либо останавливается на любом входе, либо не останавливается ни на одном входе. Таким образом, это справедливо для всех *e* и *n*. Поскольку функция *i* вычислима, это доказывает . Представленные здесь сокращения являются не только Тьюринг-сокращениями, но и многими к одному сокращениями, которые будут рассмотрены ниже.

Свойства

Каждое множество Тьюрингово эквивалентно своему дополнению. Каждое вычислимое множество Тьюрингово сводимо к любому другому множеству. Поскольку любое вычислимое множество может быть вычислено без оракула, оно может быть вычислено оракульной машиной, игнорирующей данный оракул. Отношение сводимости является транзитивным: если A ⩽T B и B ⩽T C, то A ⩽T C. Кроме того, A ⩽T A выполняется для любого множества A, и таким образом, отношение ⩽T является предпорядком (это не частный порядок, поскольку A ⩽T B и B ⩽T A не обязательно подразумевают A = B). Существуют пары множеств A и B такие, что A не Тьюрингово сводимо к B и B не Тьюрингово сводимо к A. Следовательно, ⩽T не является полным порядком. Существуют бесконечно убывающие последовательности множеств относительно ⩽T, таким образом, это отношение не является вполне упорядоченным. Каждое множество Тьюрингово сводимо к своему прыжку Тьюринга, но прыжок Тьюринга множества никогда не Тьюрингово сводим к исходному множеству.

Использование сокращения

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

Более сильные сокращения

Существует два распространенных способа получения редукций, более сильных, чем редукция Тьюринга. Первый способ – ограничить количество и способ запросов к оракулу. Множество A сводится к множеству B, если существует тотальная вычислимая функция f, такая что элемент x принадлежит A тогда и только тогда, когда f(x) принадлежит B. Такую функцию можно использовать для построения редукции Тьюринга (путем вычисления f(x), запроса к оракулу и последующей интерпретации результата). Редукция по таблице истинности или слабая редукция по таблице истинности должна представлять все свои запросы к оракулу одновременно. В редукции по таблице истинности редукция также предоставляет булеву функцию (таблицу истинности), которая, получив ответы на запросы, выдает окончательный ответ редукции. В слабой редукции по таблице истинности редукция использует ответы оракула в качестве основы для дальнейших вычислений, зависящих от полученных ответов (но не используя сам оракул). Эквивалентно, слабая редукция по таблице истинности – это редукция, для которой использование редукции ограничено вычислимой функцией. По этой причине слабые редукции по таблице истинности иногда называют «ограниченными» редукциями Тьюринга. Второй способ получения более сильного понятия редуцируемости – ограничить вычислительные ресурсы, которые может использовать программа, реализующая редукцию Тьюринга. Эти ограничения на вычислительную сложность редукции важны при изучении субрекурсивных классов, таких как P. Множество A полиномиально сводится к множеству B, если существует редукция Тьюринга из A в B, работающая за полиномиальное время. Концепция логарифмической редукции по пространству аналогична. Эти редукции сильнее в том смысле, что они обеспечивают более тонкое разделение на классы эквивалентности и удовлетворяют более строгим требованиям, чем редукции Тьюринга. Следовательно, такие редукции сложнее найти. Может не существовать способа построить редукцию «многие-к-одному» из одного множества в другое, даже если для тех же множеств существует редукция Тьюринга.

Более слабые сокращения

Согласно тезису Черча-Тьюринга, редукция Тьюринга является наиболее общей формой эффективно вычислимой редукции. Тем не менее, рассматриваются и более слабые редукции. Множество называется арифметическим в множестве , если оно определяется формулой арифметики Пеано с параметром . Множество называется гиперархиметическим в множестве , если существует рекурсивное ординальное число α, такое что оно вычислимо из α-го итерированного прыжка Тьюринга множества . Понятие относительной конструктивности является важным понятием редуцируемости в теории множеств.