Czy istnieje definitywne odniesienie do maszyn Turinga z wieloma taśmami wyroczni?

Wydaje się, że większość literatury dotyczy maszyn z pojedynczymi wyroczniami dla określonych problemów, jednak wydaje się, że istnieje kilka artykułów, które rozważają maszyny z wieloma wyroczniami. Czy istnieje dobra praca lub praca, która zawiera przegląd tego, co wiadomo o takich maszynach? W szczególności interesuje mnie P z wieloma wyroczniami.

oracles turing-machines Joe Fitzsimons
źródło

Jeśli chcesz tylko skończoną liczbę N wyroczni, możesz zdefiniować wyrocznię złożoną N-w-1 za pomocą pierwszych logów (N) bitów wyroczni złożonej, aby wskazać, która podrzędność ma być zapytana. Czy coś brakuje?

Niel de Beaudrap,

Tak, myślałem o tym. Interesują mnie jednak określone zestawy wyroczni, więc bardziej naturalne wydaje się rozpatrywanie ich osobno niż jako obiektu złożonego. Pomyślałem, że być może w tym kierunku mogą być dobre wyniki.

Joe Fitzsimons,

dla ciekawości, czy posiadanie wielu wyroczni dodaje więcej mocy obliczeniowej w stosunku do pojedynczej wyroczni? Wydaje mi się, że nie, ponieważ bierzesz wyrocznię odpowiadającą językowi w klasie najwyższej złożoności. Ponadto posiadanie stałej liczby wyroczni spowolni maszynę o stałą.

Marcos Villagra,

Jestem z komentarzem Marcosa na temat najsilniejszej wyroczni podbijającej pozostałe .. ale jestem zainteresowany tym, co miałeś na myśli!

Daniel Apon,

Czy myślisz o zezwoleniu na nieskończenie wiele wyroczni, w których TM może wybrać wyrocznię do zapytania? Przy takim układzie może istnieć interesująca różnica między zestawem wyroczni, w których każdy był zdecydowanie słabszy niż jakaś inna wyrocznia Q, a samym Q.

András Salamon,

Odpowiedzi:

Oto nowsza praca, która podaje różnicę między pojedynczymi a wieloma wyroczniami motywowanymi przez kryptografię:

Donald Beaver i Joan Feigenbaum. Ukrywanie instancji w zapytaniach wielorakich . STACS 1990. Springer Wykład Notatki z informatyki, 1990, tom 415/1990, 37-48, DOI: 10.1007 / 3-540-52282-4_30

Joshua Grochow
źródło

tylko pytanie, rozumiem, że koncepcja wielu wyroczni ma sens tylko wtedy, gdy wyroczni nie można się ze sobą połączyć ze względu na (postrzegane?) względy bezpieczeństwa?

Ahmed Masud

Oto starszy artykuł, który może Ci się przydać: Maszyny Logspace z wieloma taśmami Oracle autorstwa Nancy Lynch z MIT ( PDF ). W szczególności Twierdzenie 2.2 na stronie PDF 5 może być tym, czego szukasz. Istnieje również sekcja poświęcona hierarchiom zdefiniowanym przez różne liczby taśm Oracle na maszynę.

Zastrzeżenie po fakcie: Wygląda na podobne pytanie i (jeszcze bardziej podobna) odpowiedź została podana tutaj .

Daniel Apon
źródło