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

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

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

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

Определение

Даны два множества натуральных чисел, мы говорим , является Тьюринг к и записям

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

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

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

Для данного набора набор называется жестким по Тьюрингу, если для всех . Если дополнительно то называется полным по Тьюрингу .

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

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

Пример

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

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

  • Каждый набор эквивалентен своему дополнению по Тьюрингу.
  • Каждое вычислимое множество сводится по Тьюрингу к любому другому множеству. Поскольку любой вычислимый набор может быть вычислен без оракула, он может быть вычислен машиной оракула, которая игнорирует данный оракул.
  • Отношение транзитивное: если и потом . Более того, выполняется для любого множества A , и, таким образом, отношение является предварительным порядком (это не частичный порядок, потому что и не обязательно подразумевает ).
  • Есть пары множеств , такие , что не Тьюринг к В и Б не Тьюринг к А . Таким образом, это не полный порядок .
  • Есть бесконечные убывающие последовательности множеств под . Таким образом, это отношение не является обоснованным .
  • Каждый набор сводится по Тьюрингу к своему собственному прыжку Тьюринга , но прыжок Тьюринга набора никогда не сводится по Тьюрингу к исходному набору.

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

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

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

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

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

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

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

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

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

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

Заметки

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

  • М. Дэвис, ред., 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 .

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