Сокращение Тьюринга

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

Если сокращение Тьюринга от $A$ к $B$ существует, то каждый алгоритм для $B$ можно использовать для создания алгоритма $A$, вставив алгоритм для $B$ в каждом месте, где компьютер-оракул выполняет вычисления $A$ запрашивает у оракула $B$. Однако, поскольку оракул-машина может запрашивать оракул большое количество раз, результирующий алгоритм асимптотически может потребовать больше времени, чем любой алгоритм $B$ или машина-оракул $A$. Сокращение Тьюринга, при котором машина оракула работает за полиномиальное время , известно как сокращение Кука .

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

Определение

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

$A\leq _{T}B$

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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

• Набор $A$ сводится много-один к $B$ если существует тотальная вычислимая функция $f$ такой, что элемент $n$ находится в $A$ тогда и только тогда, когда $f(n)$ находится в $B$. Такую функцию можно использовать для генерации сокращения Тьюринга (путем вычисления $f(n)$, опрашивая оракула и затем интерпретируя результат).
• Сокращение таблицы истинности или слабое сокращение таблицы истинности должно представлять все запросы оракула одновременно. При сокращении таблицы истинности сокращение также дает логическую функцию ( таблицу истинности ), которая при получении ответов на запросы выдает окончательный ответ сокращения. При слабой редукции таблицы истинности приведение использует ответы оракула в качестве основы для дальнейших вычислений в зависимости от данных ответов (но не с использованием оракула). Аналогично, слабая редукция таблицы истинности — это такая редукция, для которой использование редукции ограничено вычислимой функцией. По этой причине слабые сокращения таблицы истинности иногда называют «ограниченными сокращениями Тьюринга».

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

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

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

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

См. также

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

Ссылки

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

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

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