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

Концепция в теории вычислимости

В теории вычислимости , сведение Тьюринга от задачи принятия решения к задаче принятия решения является машиной оракула , которая решает задачу, имея оракула для (Rogers 1967, Soare 1987). Его можно понимать как алгоритм , который можно было бы использовать для решения, если бы у него была подпрограмма для решения . Аналогично эту концепцию можно применить к задачам функций . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Если существует редукция Тьюринга от до , то каждый алгоритм для ^[a] может быть использован для создания алгоритма для , вставляя алгоритм для в каждое место, где вычислительная машина оракула запрашивает оракул для . Однако, поскольку машина оракула может запрашивать оракул большое количество раз, результирующий алгоритм может потребовать больше времени асимптотически, чем алгоритм для или вычислительная машина оракула . Редукция Тьюринга, в которой машина оракула работает за полиномиальное время, известна как редукция Кука . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

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

Определение

При наличии двух множеств натуральных чисел мы говорим, что Тьюринг сводится к и записываем ${\displaystyle A,B\subseteq \mathbb {N} }$ ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle A\leq _{T}B}$

тогда и только тогда, когда существует машина оракула , которая вычисляет характеристическую функцию A при запуске с оракулом B. В этом случае мы также говорим, что A является B -рекурсивным и B -вычислимым .

Если существует машина оракула, которая при запуске с оракулом B вычисляет частичную функцию с доменом A , то говорят, что A является B - рекурсивно перечислимым и B -вычислимо перечислимым .

Мы говорим , что эквивалентно Тьюрингу и пишем, если и то , и то Классы эквивалентности множеств, эквивалентных Тьюрингу, называются степенями Тьюринга . Степень Тьюринга множества записывается как . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\equiv _{T}B\,}$ ${\displaystyle A\leq _{T}B}$ ${\displaystyle B\leq _{T}A.}$ ${\displaystyle X}$ ${\displaystyle {\textbf {deg}}(X)}$

При наличии множества множество называется полным по Тьюрингу для , если для всех . Если дополнительно то называется полным по Тьюрингу для . ${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle X\leq _{T}A}$ ${\displaystyle X\in {\mathcal {X}}}$ ${\displaystyle A\in {\mathcal {X}}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {X}}}$

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

Полнота по Тьюрингу, как только что определено выше, лишь частично соответствует полноте по Тьюрингу в смысле вычислительной универсальности. В частности, машина Тьюринга является универсальной машиной Тьюринга, если ее проблема остановки (т. е. набор входов, для которых она в конечном итоге останавливается) является много-однополной для набора рекурсивно перечислимых множеств. Таким образом, необходимым , но недостаточным условием для того, чтобы машина была вычислительно универсальной, является то, чтобы проблема остановки машины была полной по Тьюрингу для . Недостаточно, потому что все еще может быть так, что язык, принимаемый машиной, сам по себе не является рекурсивно перечислимым. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {X}}}$

Пример

Пусть обозначает множество входных значений, для которых машина Тьюринга с индексом e останавливается. Тогда множества и эквивалентны по Тьюрингу (здесь обозначает эффективную функцию спаривания). Редукция, показывающая, что может быть построена с использованием того факта, что . Для пары новый индекс может быть построен с использованием теоремы s mn таким образом, что программа, закодированная с помощью , игнорирует свой ввод и просто имитирует вычисление машины с индексом e на входе n . В частности, машина с индексом либо останавливается на каждом вводе, либо не останавливается ни на каком вводе. Таким образом, справедливо для всех e и n . Поскольку функция i вычислима, это показывает . Представленные здесь редукции являются не только редукциями Тьюринга, но и редукциями многих единиц , обсуждаемыми ниже. ${\displaystyle W_{e}}$ ${\displaystyle A=\{e\mid e\in W_{e}\}}$ ${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$ ${\displaystyle (-,-)}$ ${\displaystyle A\leq _{T}B}$ ${\displaystyle e\in A\Leftrightarrow (e,e)\in B}$ ${\displaystyle (e,n)}$ ${\displaystyle i(e,n)}$ ${\displaystyle i(e,n)}$ ${\displaystyle i(e,n)}$ ${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$ ${\displaystyle B\leq _{T}A}$

Характеристики

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

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

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

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

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

• Множество является сводимым ко многим-одному , если существует полная вычислимая функция , такая что элемент находится в тогда и только тогда, когда находится в . Такая функция может быть использована для генерации редукции Тьюринга (вычисляя , запрашивая оракул и затем интерпретируя результат). ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle f(n)}$ ${\displaystyle B}$ ${\displaystyle f(n)}$
• Редукция таблицы истинности или слабая редукция таблицы истинности должны одновременно представлять все свои запросы оракула. ​​В редукции таблицы истинности редукция также дает булеву функцию ( таблицу истинности ), которая при наличии ответов на запросы даст окончательный ответ редукции. В слабой редукции таблицы истинности редукция использует ответы оракула в качестве основы для дальнейших вычислений в зависимости от данных ответов (но не используя оракул). Эквивалентно, слабая редукция таблицы истинности — это редукция, для которой использование редукции ограничено вычислимой функцией. По этой причине слабые редукции таблицы истинности иногда называют «ограниченными Тьюринговыми» редукциями.

Второй способ создания более сильного понятия сводимости — ограничить вычислительные ресурсы, которые может использовать программа, реализующая редукцию Тьюринга. Эти ограничения на вычислительную сложность редукции важны при изучении субрекурсивных классов, таких как P . Множество A является полиномиально сводимым к множеству, если существует редукция Тьюринга к , которая выполняется за полиномиальное время. Концепция логарифмической редукции аналогична. ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

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

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

Согласно тезису Чёрча–Тьюринга , редукция Тьюринга является наиболее общей формой эффективно вычислимой редукции. Тем не менее, рассматриваются и более слабые редукции. Множество называется арифметическим в , если определяется формулой арифметики Пеано с в качестве параметра. Множество является гиперарифметическим в , если существует рекурсивный ординал такой, что вычислим из , α -итерированного скачка Тьюринга . Понятие относительной конструктивности является важным понятием сводимости в теории множеств . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle B^{(\alpha )}}$ ${\displaystyle B}$

Смотрите также

• Сокращение карпа

Примечания

1. Возможно, что B — неразрешимая задача , для которой не существует алгоритма.

Ссылки

• M. Davis, ed., 1965. Неразрешимое — основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях , Raven, New York. Переиздание, Dover, 2004. ISBN  0-486-43228-9 .
• SC Kleene, 1952. Введение в метаматематику. Амстердам: Северная Голландия.
• SC Kleene и EL Post, 1954. «Верхняя полурешетка степеней рекурсивной неразрешимости». Annals of Mathematics т. 2 прим. 59, 379–407.
• Post, EL (1944). "Рекурсивно перечислимые множества положительных целых чисел и проблемы их принятия решений" ( PDF ) . Бюллетень Американского математического общества . 50 (5): 284–316. doi : 10.1090/s0002-9904-1944-08111-1 . Получено 17.12.2015 .
• А. Тьюринг, 1939. «Системы логики, основанные на ординалах». Труды Лондонского математического общества , сер. 2 т. 45, стр. 161–228. Перепечатано в «Неразрешимое», под ред. М. Дэвиса, 1965.
• Х. Роджерс , 1967. Теория рекурсивных функций и эффективная вычислимость. McGraw-Hill.
• Р. Соаре , 1987. Рекурсивно перечислимые множества и степени, Springer.
• Дэвис, Мартин (ноябрь 2006 г.). «Что такое... сводимость по Тьюрингу?» (PDF) . Notices of the American Mathematical Society . 53 (10): 1218–1219 . Получено 16.01.2008 .

Внешние ссылки

• Словарь алгоритмов и структур данных NIST: Редукция Тьюринга
• Кембриджский университет, Эндрю Питтс, Тобиас Кон: Теория вычислений
• Домашняя страница профессора Жана Галлье