Сводимость перечисления

В теории вычислимости сводимость перечисления (или e-сводимость сокращенно ) представляет собой особый тип сводимости . Грубо говоря, A сводимо перечислением к B, перечисление B может быть алгоритмически преобразовано в перечисление A. если В частности, если B вычислимо перечислимо , то и A тоже.

Введение

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

если возможно перечислить B , то это можно использовать для перечисления A. Сводимость перечисления — это вариант, неформальное объяснение которого заключается в том, что Сокращение может быть определено машиной Тьюринга с помощью специальной инструкции запроса оракула, которая не принимает параметров и либо возвращает новый элемент B , либо не возвращает никаких результатов. Оракул поставляет элементы B в любом порядке. Возможно, он не вернет никаких результатов для некоторых запросов, прежде чем возобновит перечисление. Машина должна аналогичным образом обрабатывать элементы A в любом порядке и в любом темпе. ^[1] Повторы в перечислениях A и B могут быть разрешены или нет; концепция эквивалентна в обоих случаях. Хотя это можно уточнить, приведенное ниже определение является более распространенным, поскольку формально оно проще.

Сводимость перечисления — это форма положительной сводимости в том смысле, что оракул-машина получает информацию о том, какие элементы находятся в B (положительная информация), но не получает информации о том, какие элементы не находятся в B (отрицательная информация). Действительно, если элемент еще не внесен в список, машина-оракул не может знать, будет ли он внесен в список позже или никогда.

Концепция сводимости перечисления была впервые введена в результате результатов Джона Майхилла , который пришел к выводу, что «множество является полным тогда и только тогда, когда оно рекурсивно перечислимо , а его дополнение продуктивно». ^[2] Этот результат распространяется и на сводимость перечисления. ^{[ нужна ссылка ]} Сводимость перечисления была позже официально систематизирована Роджерсом и его сотрудником Ричардом М. Фридбергом в журнале «Математическая логика и основы математики» (предшественник журнала Mathematical Logic Quarterly ) в 1959 году. ^[3]

Определение ^[4]

Позволять $(D_{u})$ — стандартная нумерация конечных подмножеств $\mathbb {N}$ , и пусть $\langle \bullet ,\bullet \rangle$ быть стандартной функцией сопряжения . Набор $A\subseteq \mathbb {N}$ сводится ли перечисление к множеству $B\subseteq \mathbb {N}$ если существует вычислимо перечислимое множество $W$ такой, что для всех $x\in \mathbb {N}$ ,

x\in A\iff \exists u,(D_{u}\subseteq B\land \langle x,D\rangle \in W)

Когда A является перечислением, сводящимся к B , мы пишем $A\leq _{e}B$ . Отношение $\leq _{e}$ это предзаказ . Связанное с ним отношение эквивалентности обозначается через $\equiv _{e}$ . ^[5]

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

Супремум ( наименьшая верхняя граница, соединение) множеств $A$ и $B$ относительно $\leq _{e}$ задается непересекающимся союзом

A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}.

^[6]

A сводимо по Тьюрингу к B тогда и только тогда, когда $A^{+}$ сводится ли перечисление к $B^{+}$ , где оператор плюс определяется как $A^{+}:=A\oplus {\overline {A}}$ . ^[6] Неформально этот оператор кодирует положительную и отрицательную информацию об А положительным образом. Аналогично, A вычислимо перечислимо с помощью оракула B тогда и только тогда, когда A является перечислением, сводимым к $B^{+}$ .

Более того, A является перечислением, сводимым к B тогда и только тогда, когда для всех X таких, что вычислимо перечислимо с оракулом X , справедливо, что A также вычислимо перечислимо с оракулом X. B Это теорема Сельмана .

Варианты

Сильная сводимость перечисления

Помимо сводимости перечисления, существуют сильные версии, наиболее важной из которых является s -сводимость (названная в честь Роберта М. Соловея ). S -сводимость утверждает, что вычислимо перечислимое действительное множество $A$ является s -сводимым к другому вычислимо перечислимому действительному множеству $B$ если $B$ по крайней мере так же сложно поддается аппроксимации, как $A$ . ^[7] Этот метод демонстрирует сходство с e -сводимостью в том, что он сравнивает элементы нескольких наборов. Кроме того, структура s -степеней имеет естественные аналоги в степенях нумерации. ^[6]

Обоснование использования s -сводимости резюмировано Омандазе и Сорби как результат того, что модели положительной сводимости не могут ответить на некоторые вопросы оракула (например, ответ на вопрос «Является ли $x\in A$ ?" ставится только в том случае, если $x\in A$ , и не верно для обратного.), потому что они по своей сути моделируют вычислительные ситуации, когда доступна неполная информация оракула. ^[8] Это контрастирует с хорошо изученной сводимостью Тьюринга , в которой информация фиксируется как в отрицательных, так и в положительных значениях. Кроме того, T-сводимость использует информацию, предоставляемую немедленно и без задержки. Сильная сводимость используется для предотвращения проблем, возникающих при предоставлении неполной информации.

Частичные функции

E -сводимость может быть определена для частичных функций и . Написание графика $(f)=\{\langle x,y\rangle$ $|$ $f(x)=y\}$ и т. д. мы можем определить для частичных функций $f,g$ : ^[9]

f\leq _{e}g\Leftrightarrow

график

(f)\leq _{e}

график

(g).

Теорема Клини о рекурсии вводит понятие относительной частичной рекурсивности , которая с помощью систем уравнений может демонстрировать эквивалентность через $\leq _{e}$ между графиками частичных функций. ^[10] E -сводимость относится к относительной частичной рекурсивности таким же образом, как T-сводимость относится к μ-рекурсивности . ^[6]

См. также

Ссылки

^ Шенфилд, младший (июль 1969 г.). «Теория рекурсивных функций и эффективная вычислимость (Хартли Роджерс-младший)» . Обзор СИАМ . 11 (3): 415–416. дои : 10.1137/1011079 . ISSN 0036-1445 .
^ Майхилл, Джон (1961). «Замечание о степенях частичных функций» . Труды Американского математического общества . 12 (4): 519–521. дои : 10.1090/S0002-9939-1961-0125794-X . ISSN 0002-9939 .
^ Сакс, Джеральд Э. (декабрь 1960 г.). «Ричард М. Фридберг и Хартли Роджерс-младший, Сводимость и полнота наборов целых чисел. Журнал математической логики и основ математики, том 5 (1959), стр. 117–125» . Журнал символической логики . 25 (4): 362–363. дои : 10.2307/2963569 . ISSN 0022-4812 . JSTOR 2963569 . S2CID 124102995 .
^ Харрис, Чарльз Милтон (2006). Сводимость перечисления и полиномиальное время . CiteSeerX 10.1.1.95.8166 .
^ Кейс, Джон (1 февраля 1971 г.). «Сводимость перечисления и частичные степени». Анналы математической логики . 2 (4): 419–439. дои : 10.1016/0003-4843(71)90003-9 . ISSN 0003-4843 .
^ Перейти обратно: ^а ^б ^с ^д Соскова Александра А.; Соскова, Мария И. (2017), День, Адам; Ребята, Майкл; Гринберг, Ноам; Хусаинов, Бахадыр (ред.), «Сводимость перечисления и теория вычислимых структур» , Вычислимость и сложность: очерки, посвященные Родни Дж. Дауни по случаю его 60-летия , Конспекты лекций по информатике, том. 10010, Чам: Springer International Publishing, стр. 271–301, doi : 10.1007/978-3-319-50062-1_19 , ISBN. 978-3-319-50062-1 , получено 18 декабря 2020 г.
^ Чжэн, Сичжун; Реттингер, Роберт (2004). «О расширениях Соловея-приводимости» . В Чва, Кён Ён; Манро, Дж. Ян Дж. (ред.). Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 3106. Берлин, Гейдельберг: Springer. стр. 360–369. дои : 10.1007/978-3-540-27798-9_39 . ISBN 978-3-540-27798-9 .
^ Оманадзе, Роланд Ш.; Сорби, Андреа (01 октября 2006 г.). «Сильная сводимость перечисления» . Архив математической логики . 45 (7): 869–912. дои : 10.1007/s00153-006-0012-4 . ISSN 1432-0665 . S2CID 44764613 .
^ Купер, С. Барри (1990). «Сводимость перечисления, недетерминированные вычисления и относительная вычислимость частичных функций» . В Амбос-Списе, Клаус; Мюллер, Герт Х.; Сакс, Джеральд Э. (ред.). Неделя теории рекурсии . Конспект лекций по математике. Том. 1432. Берлин, Гейдельберг: Springer. стр. 57–110. дои : 10.1007/BFb0086114 . ISBN 978-3-540-47142-4 .
^ Клини, Стивен Коул, 1909–1994 гг. (1971). Введение в метаматематику . Гронинген: паб Wolters-Noordhoff. ISBN 0-7204-2103-9 . OCLC 768949 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

Дальнейшее чтение

Введение в метаматематику

«Теория рекурсивных функций и эффективная вычислимость»

Сводимость перечисления и полиномиальное время

[1] Шенфилд, младший (июль 1969 г.). «Теория рекурсивных функций и эффективная вычислимость (Хартли Роджерс-младший)» . Обзор СИАМ . 11 (3): 415–416. дои : 10.1137/1011079 . ISSN 0036-1445 .

[2] Майхилл, Джон (1961). «Замечание о степенях частичных функций» . Труды Американского математического общества . 12 (4): 519–521. дои : 10.1090/S0002-9939-1961-0125794-X . ISSN 0002-9939 .

[3] Сакс, Джеральд Э. (декабрь 1960 г.). «Ричард М. Фридберг и Хартли Роджерс-младший, Сводимость и полнота наборов целых чисел. Журнал математической логики и основ математики, том 5 (1959), стр. 117–125» . Журнал символической логики . 25 (4): 362–363. дои : 10.2307/2963569 . ISSN 0022-4812 . JSTOR 2963569 . S2CID 124102995 .

[4] Харрис, Чарльз Милтон (2006). Сводимость перечисления и полиномиальное время . CiteSeerX 10.1.1.95.8166 .

[5] Кейс, Джон (1 февраля 1971 г.). «Сводимость перечисления и частичные степени». Анналы математической логики . 2 (4): 419–439. дои : 10.1016/0003-4843(71)90003-9 . ISSN 0003-4843 .

[:4-6] Перейти обратно: ^а ^б ^с ^д Соскова Александра А.; Соскова, Мария И. (2017), День, Адам; Ребята, Майкл; Гринберг, Ноам; Хусаинов, Бахадыр (ред.), «Сводимость перечисления и теория вычислимых структур» , Вычислимость и сложность: очерки, посвященные Родни Дж. Дауни по случаю его 60-летия , Конспекты лекций по информатике, том. 10010, Чам: Springer International Publishing, стр. 271–301, doi : 10.1007/978-3-319-50062-1_19 , ISBN. 978-3-319-50062-1 , получено 18 декабря 2020 г.

[7] Чжэн, Сичжун; Реттингер, Роберт (2004). «О расширениях Соловея-приводимости» . В Чва, Кён Ён; Манро, Дж. Ян Дж. (ред.). Вычисления и комбинаторика . Конспекты лекций по информатике. Том. 3106. Берлин, Гейдельберг: Springer. стр. 360–369. дои : 10.1007/978-3-540-27798-9_39 . ISBN 978-3-540-27798-9 .

[:1-8] Оманадзе, Роланд Ш.; Сорби, Андреа (01 октября 2006 г.). «Сильная сводимость перечисления» . Архив математической логики . 45 (7): 869–912. дои : 10.1007/s00153-006-0012-4 . ISSN 1432-0665 . S2CID 44764613 .

[9] Купер, С. Барри (1990). «Сводимость перечисления, недетерминированные вычисления и относительная вычислимость частичных функций» . В Амбос-Списе, Клаус; Мюллер, Герт Х.; Сакс, Джеральд Э. (ред.). Неделя теории рекурсии . Конспект лекций по математике. Том. 1432. Берлин, Гейдельберг: Springer. стр. 57–110. дои : 10.1007/BFb0086114 . ISBN 978-3-540-47142-4 .

[:2-10] Клини, Стивен Коул, 1909–1994 гг. (1971). Введение в метаматематику . Гронинген: паб Wolters-Noordhoff. ISBN 0-7204-2103-9 . OCLC 768949 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка ) CS1 maint: числовые имена: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]