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

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

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

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

• 1 Определение
  • 1.1 Связь полноты по Тьюрингу с вычислительной универсальностью
• 2 Пример
• 3 свойства
• 4 Использование редукции
• 5 Более сильные скидки
• 6 более слабые сокращения
• 7 См. Также
• 8 Примечания
• 9 ссылки
• 10 Внешние ссылки

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

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

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

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

Мы говорим это Тьюринг эквивалент к и записи, если оба и В классы эквивалентности Тьюринга эквивалентных множеств называется Turing градусов. Тьюринг степень набора записывается. ${\ displaystyle A}$${\ displaystyle B}$${\ Displaystyle А \ эквив _ {Т} В \,}$${\ displaystyle A \ leq _ {T} B}$${\ displaystyle B \ leq _ {T} A.}$ ${\ displaystyle X}$${\ displaystyle {\ textbf {deg}} (X)}$

Для данного набора набор называется жестким по Тьюрингу, если для всех. Если дополнительно то называется полным по Тьюрингу. ${\ Displaystyle {\ mathcal {X}} \ substeq {\ mathcal {P}} (\ mathbb {N})}$${\ Displaystyle А \ substeq \ 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}}}$

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

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

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

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

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

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

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

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

• М. Дэвис, ред., 1965. Неразрешимые - основные статьи о неразрешимых предложениях, неразрешимых задачах и вычислимых функциях, Рэйвен, Нью-Йорк. Перепечатка, Довер, 2004. ISBN   0-486-43228-9.
• SC Kleene, 1952. Введение в метаматематику. Амстердам: Северная Голландия.
• SC Kleene, EL Post, 1954. "Верхняя полурешетка степеней рекурсивной неразрешимости". Анналы математики v. 2 n. 59, 379–407.
• Пост, Э.Л. (1944). «Рекурсивно перечислимые множества натуральных чисел и проблемы их решения» ( PDF ). Бюллетень Американского математического общества. 50: 284–316. DOI : 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: редукция по Тьюрингу