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

В теория вычислимости, а Редукция Тьюринга из проблема решения А к проблеме решения B является машина оракула который решает проблему А дан оракул для B (Роджерс 1967, Соар 1987). Это можно понимать как алгоритм что можно использовать для решения А если бы в его распоряжении был подпрограмма для решения B. Аналогичным образом это понятие можно применить к функциональные проблемы.

Если редукция Тьюринга от А к B существует, то каждый алгоритм за B^[а] может быть использован для создания алгоритма для А, вставив алгоритм для B в каждом месте, где компьютер оракула вычисляет А запрашивает у оракула B. Однако, поскольку машина оракула может запрашивать оракула большое количество раз, результирующий алгоритм может асимптотически потребовать больше времени, чем любой алгоритм для B или компьютерные вычисления оракула А. Редукция Тьюринга, в которой машина оракула работает за полиномиальное время, известна как Уменьшение повара.

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

Определение

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

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

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

Если есть машина оракула, которая при запуске с оракулом B, вычисляет частичную функцию с областью определения А, тогда А как говорят 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 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)}$ можно построить с помощью s_мин теорема так что программа закодирована ${\displaystyle i(e,n)}$ игнорирует его ввод и просто имитирует вычисление машины с индексом е на входе п. В частности, машина с индексом ${\displaystyle i(e,n)}$ либо останавливается при каждом вводе, либо останавливается при отсутствии ввода. Таким образом ${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$ относится ко всем е и п. Поскольку функция я вычислимо, это показывает ${\displaystyle B\leq _{T}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}$).
• Есть пары наборов ${\displaystyle (A,B)}$ такой, что А не сводится по Тьюрингу к B и B не сводится по Тьюрингу к А. Таким образом ${\displaystyle \leq _{T}}$ это не общий заказ.
• Имеются бесконечные убывающие последовательности множеств под ${\displaystyle \leq _{T}}$. Таким образом, это отношение не обоснованный.
• Каждый набор сводится по Тьюрингу к своему собственному Прыжок Тьюринга, но скачок Тьюринга набора никогда не сводится по Тьюрингу к исходному набору.

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

Поскольку каждое сокращение из набора B к набору А должен определить, находится ли один элемент в А всего за конечное количество шагов, он может сделать только конечное количество запросов членства в множестве B. Когда количество информации о наборе B используется для вычисления одного бита А обсуждается, это уточняется функцией использования. Формально использовать редукции - это функция, которая отправляет каждое натуральное число п к наибольшему натуральному числу м членство в наборе B был запрошен сокращением при определении членства п в А.

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

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

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

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

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

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

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

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

• Редукция Карпа

Примечания

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

Рекомендации

• М. Дэвис, изд., 1965. Неразрешимые: основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях, Рэйвен, Нью-Йорк. Перепечатка, Дувр, 2004. ISBN  0-486-43228-9.
• С. К. Клини, 1952. Введение в метаматематику. Амстердам: Северная Голландия.
• С. К. Клини, Э. Л. Пост, 1954. "Верхняя полурешетка степеней рекурсивной неразрешимости". Анналы математики v. 2 п. 59, 379–407.
• Пост, Э. (1944). «Рекурсивно перечислимые множества натуральных чисел и проблемы их решения» (PDF ). Бюллетень Американского математического общества. 50: 284–316. Дои:10.1090 / с0002-9904-1944-08111-1. Получено 2015-12-17.
• А. Тьюринг, 1939. «Логические системы на основе ординалов». Труды Лондонского математического общества, сер. 2 т. 45, стр. 161–228. Перепечатано в «Неразрешимом», изд. М. Дэвиса, 1965.
• Х. Роджерс, 1967. Теория рекурсивных функций и эффективная вычислимость. Макгроу-Хилл.
• Р. Соаре, 1987. Рекурсивно перечислимые множества и степени, Springer.
• Дэвис, Мартин (Ноябрь 2006 г.). "Что такое ... сводимость Тьюринга?" (PDF ). Уведомления Американского математического общества. 53 (10): 1218–1219. Получено 2008-01-16.

внешняя ссылка

• Словарь алгоритмов и структур данных NIST: редукция по Тьюрингу