Есть ли точная ссылка на машины Тьюринга с несколькими оракульными лентами?

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

oracles turing-machines Джо Фитцсимонс
источник

Если вам нужно только конечное число оракулов N, вы можете определить составной оракул N-in-1, используя первые лог (N) биты составного оракула, чтобы указать, какой субракул вы хотите запросить. Я что-то пропустил?

Ниль де Бодрап,

Да, я думал об этом. Однако меня интересуют конкретные наборы оракулов, и поэтому более естественно рассматривать их отдельно, чем как составной объект. Я подумал, что, возможно, в этом направлении могут быть хорошие результаты.

Джо Фицсимонс

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

Маркос Вильягра

Я с комментарием Маркоса о сильнейшем оракуле, который покорил остальных ... но мне интересно, что вы имели в виду сейчас!

Даниэль Апон

Думаете ли вы о том, чтобы разрешить бесконечно много оракулов, когда ТМ может выбирать, какого оракула запрашивать? При такой установке может быть интересное различие между набором оракулов, в которых каждый был строго слабее, чем какой-либо другой оракул Q, и самим Q.

Андрас Саламон

Ответы:

Вот более поздняя статья, в которой дается различие между одним и несколькими оракулами, мотивированными криптографией:

Дональд Бивер и Джоан Фейгенбаум. Скрытие экземпляров в многоракулевых запросах . STACS 1990. Лекционные заметки Спрингера по информатике, 1990, том 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

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

просто вопрос, я так понимаю, что концепция мультиракула имеет смысл только в том случае, если оракулы не могут быть свернуты друг в друга по каким-то (предполагаемым?) причинам безопасности?

Ахмед Масуд

Вот более старая статья, которая может оказаться вам полезной: «Машины пространства журналов с несколькими лентами Oracle» Нэнси Линч из Массачусетского технологического института ( PDF ). В частности, теорема 2.2 на PDF-странице 5 может быть тем, что вы ищете. Есть также раздел об иерархиях, определяемых различным количеством оракульных лент на машину.

Отказ от ответственности за факт: Похоже, похожий вопрос и (еще более похожий) ответ были даны здесь .

Даниэль Апон
источник