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

Понятие теории вычислимости

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

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

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

Определение

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

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

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

Если существует машина-оракул, которая при запуске с оракулом B вычисляет частичную функцию с областью определения A , то A называется 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}}}$

Пример

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

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

• Каждое множество эквивалентно по Тьюрингу своему дополнению.
• Каждое вычислимое множество сводится по Тьюрингу к любому другому множеству. Поскольку любое вычислимое множество можно вычислить без оракула, оно может быть вычислено с помощью машины-оракула, которая игнорирует данный оракул.
• Отношение транзитивно: if и then . Более того, это справедливо для любого множества 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}$
• Существуют пары множеств , такие что A не сводимо по Тьюрингу к B , а B не сводимо по Тьюрингу к A. Таким образом, это не полный порядок . ${\displaystyle (A,B)}$ ${\displaystyle \leq _{T}}$
• Существуют бесконечные убывающие последовательности множеств под . Таким образом, эта связь не вполне обоснована . ${\displaystyle \leq _{T}}$
• Каждое множество сводится по Тьюрингу к своему собственному тьюринговскому прыжку , но тьюринговский прыжок множества никогда не сводится по Тьюрингу к исходному множеству.

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Возможно, 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: сокращение Тьюринга
• Кембриджский университет, Эндрю Питтс, Тобиас Кон: Теория вычислений
• Домашняя страница профессора Жана Галье