В теории вычислимости , с уменьшением Тьюринга от проблемы решения к проблеме решения это оракульная машина, которая решает проблемы дан оракул для (Роджерс 1967, Соар 1987). Его можно понять как алгоритм, который можно использовать для решенияесли она имела в своем распоряжении в подпрограмму для решения B . Эту концепцию можно аналогичным образом применить к функциональным задачам .
Если редукция Тьюринга от к существует, то любой алгоритм для B [a] может быть использован для создания алгоритма для, вставив алгоритм для в каждом месте, где машина-оракул, вычисляющая A, запрашивает у оракула. Однако, поскольку машина оракула может запрашивать оракула большое количество раз, результирующий алгоритм может асимптотически потребовать больше времени, чем любой алгоритм для или компьютерные вычисления оракула . Редукция Тьюринга, при которой машина оракула работает за полиномиальное время, известна как редукция Кука .
Первое формальное определение относительной вычислимости, которое тогда называлось относительной сводимостью, было дано Аланом Тьюрингом в 1939 году в терминах машин-оракулов . Позже, в 1943 и 1952 годах, Стивен Клини определил эквивалентное понятие в терминах рекурсивных функций . В 1944 году Эмиль Пост использовал термин «сводимость Тьюринга» для обозначения этой концепции.
Определение
Учитывая два набора натуральных чисел, мы говорим является Тьюринг к и писать
если есть оракул машина , которая вычисляет характеристическую функцию из А при запуске с оракулом B . В этом случае мы также говорим , является B -recursive и B -вычислимый .
Если существует машина-оракул, которая при запуске с оракулом B вычисляет частичную функцию с областью A , то A называется B - рекурсивно перечислимым и B -вычислимо перечислимым .
Мы говорим является Тьюринг эквивалент для и писать если оба а также Эти классы эквивалентности Тьюринг эквивалентных множеств называются тьюринг градусов . Степень Тьюринга множества написано .
Учитывая набор , множество называется трудным по Тьюрингу за если для всех . Если дополнительно тогда называется полным по Тьюрингу для.
Связь полноты по Тьюрингу с вычислительной универсальностью
Полнота по Тьюрингу, как только что определено выше, лишь частично соответствует полноте по Тьюрингу в смысле вычислительной универсальности. В частности, машина Тьюринга является универсальной машиной Тьюринга, если ее проблема остановки (т. Е. Набор входных данных, для которых она в конечном итоге останавливается) полна "много-один" . Таким образом, необходимое, но недостаточное условие для вычислительной универсальности машины состоит в том, чтобы проблема остановки машины была полной по Тьюрингу для множества рекурсивно перечислимых множеств.
Пример
Позволять обозначают набор входных значений, при которых машина Тьюринга с индексом e останавливается. Тогда наборы а также эквивалентны Тьюрингу (здесь обозначает эффективную функцию спаривания). Уменьшение показывает можно построить, используя тот факт, что . Учитывая пару, новый индекс можно построить с помощью теоремы s mn так , что программа, кодируемаяигнорирует его ввод и просто имитирует вычисление машины с индексом e на входе n . В частности, машина с индексомлибо останавливается при каждом вводе, либо останавливается при отсутствии ввода. Таким образомвыполняется для всех e и n . Поскольку функция i вычислима, это показывает. Представленные здесь редукции - это не только редукции по Тьюрингу, но и редукции по принципу " много-один" , обсуждаемые ниже.
Характеристики
- Каждый набор эквивалентен своему дополнению по Тьюрингу.
- Каждое вычислимое множество сводится по Тьюрингу к любому другому множеству. Поскольку любой вычислимый набор может быть вычислен без оракула, он может быть вычислен машиной оракула, которая игнорирует данный оракул.
- Соотношение транзитивен: если а также тогда . Более того,выполняется для любого множества A , и, следовательно, соотношениеэто предварительный заказ (это не частичный заказ, потому что а также не обязательно подразумевает ).
- Есть пары наборов таким образом, что не Тьюринг сводится к B и B не Тьюринг сводится к А . Таким образомэто не полный заказ .
- Имеются бесконечные убывающие последовательности множеств под . Таким образом, это отношение не является обоснованным .
- Каждый набор сводится по Тьюрингу к своему собственному прыжку Тьюринга , но прыжок Тьюринга набора никогда не сводится по Тьюрингу к исходному набору.
Использование сокращения
Поскольку каждое сокращение из набора к набору должен определить, находится ли один элемент в всего за конечное количество шагов, он может сделать только конечное количество запросов о членстве в множестве . Когда количество информации о наборе используется для вычисления одного бита обсуждается, это уточняется функцией использования. Формально, использование об уменьшении это функция , которая отправляет каждое натуральное число к наибольшему натуральному числу членство которого в множестве B было запрошено редукцией при определении принадлежности в .
Более сильные сокращения
Есть два распространенных способа получения редукций, более сильных, чем сводимость по Тьюрингу. Первый способ - ограничить количество и манеру запросов оракула.
- Набор это много-один сводимы кесли есть полная вычислимая функция такой, что элемент в если и только если в . Такую функцию можно использовать для генерации редукции Тьюринга (путем вычисления, запрашивая оракул, а затем интерпретируя результат).
- Сокращение таблицы истинности или слабая истина редукция таблицы должно представить все его оракул запросов одновременно. При редукции таблицы истинности редукция также дает логическую функцию ( таблицу истинности ), которая при получении ответов на запросы дает окончательный ответ редукции. При слабой редукции таблицы истинности редукция использует ответы оракула в качестве основы для дальнейших вычислений в зависимости от данных ответов (но без использования оракула). Эквивалентно, слабая редукция таблицы истинности - это такая редукция, для которой использование редукции ограничено вычислимой функцией. По этой причине слабые сокращения таблицы истинности иногда называют «ограниченными редукциями Тьюринга».
Второй способ создать более сильное понятие сводимости - ограничить вычислительные ресурсы, которые может использовать программа, реализующая редукцию Тьюринга. Эти ограничения по сложности вычислений сокращения имеют важное значение при изучении subrecursive классов , таких как P . Набор является полиномиально сводима к набору если есть редукция по Тьюрингу к который выполняется за полиномиальное время. Концепция уменьшения логического пространства аналогична.
Эти сокращения сильнее в том смысле, что они обеспечивают более тонкое различие классов эквивалентности и удовлетворяют более строгим требованиям, чем редукции Тьюринга. Следовательно, такие сокращения найти труднее. Может не быть способа построить редукцию «многие единицы» от одного набора к другому, даже если редукция Тьюринга для тех же наборов существует.
Более слабые сокращения
Согласно тезису Черча – Тьюринга редукция Тьюринга является наиболее общей формой эффективно вычислимой редукции. Тем не менее, рассматриваются и более слабые редукции. Наборсчитается арифметическим в если определима формулой арифметики Пеано скак параметр. Наборявляется гиперарифметическим в если есть рекурсивный порядковый такой, что вычислимо из , α-итерированный скачок Тьюринга . Понятие относительной конструктивности - важное понятие сводимости в теории множеств.
Смотрите также
Заметки
- ^ Возможно, что 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: редукция по Тьюрингу