Есть ли в теории вычислимости результат, который не релятивизируется?

Я читал статью Андрея Бауэра « Первые шаги в теории синтетической вычислимости» . В заключении он отмечает, что

Наша аксиоматизация имеет свой предел: она не может доказать какие-либо результаты в теории вычислимости, которые не могут относиться к вычислениям оракула. Это так, потому что теория может быть интерпретирована в варианте эффективного топоса, построенного из частично рекурсивных функций с доступом к оракулу.

Это заставило меня задуматься о нерелятивизирующих результатах в вычислимости. Все результаты, которые я знаю из теории вычислимости, относятся к вычислениям с оракулами.

Есть ли в теории вычислимости результаты, которые не релятивизируются? Т.е. результаты, которые верны для вычислимости, но не верны для вычислимости относительно какого-то оракула?

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

Также интересно узнать, можно ли сформулировать результат на языке теории синтетической вычислимости или нет.

computability relativization анонимное
источник

Все знают о нерелятивизирующих результатах в теории сложности, таких как IP = PSPACE. Я спрашиваю о нерелятивизирующих результатах теории вычислимости , а не о результатах теории сложности .

Аноним

@Erfan: Ваши комментарии не имеют отношения к вопросу. Мой вопрос о теории вычислимости, вы говорите о теории сложности. Я ищу нерелитивизирующие результаты, теорема о иерархии времени действительно релятивизируется. Если у вас есть вопрос о теореме иерархии времени и релятивизации, вы можете опубликовать отдельный вопрос.

Аноним

Соответствующий материал: гипотеза об однородности, сформулированная Г. Роджерсом, была опровергнута в книге Ричарда А. Шора; Гипотеза об однородности (1979): существует степень Тьюринга такая, что не изоморфна (структуре степеней Тьюринга с частичным заказ ). См. Аналогичный вопрос на lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Марцио Де

Хороший вопрос :-)

Андрей Бауэр

@ Марцио: Интересно. « Таким образом, это означает, что в языке есть предложение первого порядка содержащее только что верно для степеней Тьюринга, но неверно, если вы относите предложение к степеням Тьюринга для некоторого (и, конечно, работа в степенях Тьюринга эквивалентна предоставлению всем машинам Тьюринга доступа к как оракулу. Следовательно, доказательство того, что является истинным, нельзя соотнести с . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$

"Но самом деле не является результатом теория вычислимости, она составлена для мета теоремы.

φ

$\varphi$

Аноним

Ответы:

Теорема вложения Хигмана. Конечно порожденные вычислимо представимые группы - это в точности конечно порожденные подгруппы конечно представленных групп. Кроме того, каждая вычислимо представленная группа (даже те, которые счетно порождены) является подгруппой конечно представленной группы.

Обратите внимание, что это утверждение может относиться к следующему: « вычислимо представленные группы (с некоторым оракулом ) - это в точности конечно порожденные подгруппы конечно-представленных групп», но это не так, поскольку можно доказать, что для некоторых невычислимых существуют - вычислимо представленные группы, которые не вычислимы. $O$ $O$ $O$ $O$

На самом деле, я думаю , что любой не-релятивизацией результат теории вычислимости должен иметь что - то этот аромат, так как некоторые части результата или его доказательство должны какой - то образом «прибить» истинную вычислимость из вычислимости с оракулом . В этом случае именно конечность ограничивает «фактическую вычислимость». Обратите внимание, что, как просил Скотт Ааронсон, этот результат инвариантен к любой из обычных моделей вычислений (машина Тьюринга, ОЗУ и т. Д.), Но не релятивизируется (опять же, потому что все обычные модели «фактических» вычислений разделяют некоторые общее "свойство конечности"). $O$

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

Джошуа Грохов
источник

Это конечность (против бесконечности), которая отличает ваш пример, или счетность (против неисчислимости)?

Саламон

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

Андрей Бауэр

Упс, пожалуйста, замените «конечно сгенерированный» на «конечно представленный» в моем вопросе. Это была тривиальная ошибка. Что меня интересует, так это то, можем ли мы заменить «конечно представленный» чем-то более общим.

Андрей Бауэр

@ AndrewMorgan: я согласен с началом вашего спора, но не согласен с вашим выводом. Часто бывает весьма полезно , что

является

-полном. Я не считаю релятивизацию Кука-Левина совершенно неестественной ... Мне очень нравится предложение Андрея, и мы подумаем над этим ...

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

Джошуа

@AndrewMorgan: Согласен. Я думаю, что этот узел будет хорошим кандидатом :).

Джошуа

Это то, о чем я часто задумывался!

Если под «результатами в теории вычислимости» вы подразумеваете результаты, инвариантные относительно выбора модели машины (машины Тьюринга, машины с ОЗУ и т. Д.), То я не знаю ни одного примера такого результата, и я определенно вспомнил бы, если бы я видел один.

Наиболее близкий, который я могу предложить к ответу: я думаю, что в теории вычислимости есть много интересных вопросов, которые могут зависеть от модели машины. Например: функция Busy Beaver с ее обычным определением в терминах машин Тьюринга бесконечно часто нечетна? Является ли значение BB (20) независимым от ZFC? Какими бы ни были ответы на эти вопросы, они, несомненно, могут отличаться для релятивизированных аналогов функции BB.

Скотт Ааронсон
источник

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

Есть и много других примеров. Просто поиграйте с моделью вычислений, и вы сможете найти другие похожие результаты.

Филип Уайт
источник

Просто любопытно: что именно не так с этим ответом? Возможно, downvoters не верят, что возможно запретить машине Тьюринга доступ к оракулу, и требуют дальнейшего объяснения этого?

Филипп Уайт

Не похоже, чтобы было достаточно справедливое определение релятивизации, позволяющее машине иметь оракула, но не позволяющее ей использовать оракула.

Дэвид Эппштейн

Интересно, хотя и не то, что я ищу. Я ищу известный результат в теории вычислимости, который не релятивизируется, а не аргумент в пользу того, как создать такой результат.

Аноним

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

Каве

Возьмите, например, метод релятивизации в BGS. Это интересно, потому что он сохраняет простые аргументы диагонализации, поэтому они не могут сопоставить P и NP. Если релятивизация не сохраняет такие аргументы, то это, вероятно, не интересный способ релятивизации утверждений. Хорошая релятивизация должна выдерживать как можно больше известных аргументов и доказанных результатов, чем меньше она сохраняет, тем менее интересной она становится.

Каве