<p>Here is a more recent paper giving a difference between single vs. multiple oracles motivated by cryptography:</p>
<p>Donald Beaver and Joan Feigenbaum.  <a href="https://doi.org/10.1007/3-540-52282-4_30" rel="nofollow noreferrer">Hiding instances in multioracle queries</a>.  STACS 1990.  Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007/3-540-52282-4_30</p>

CC BY-SA 3.0
2011-12-14T09:37:11.387Z
just a question, i take it that the concept of multi-oracle only makes sense if the oracles cannot be collapsed into each other for some (perceived?) security reasons?
Ahmed Masud
CC BY-SA 4.0
2010-08-19T16:10:03.350Z
2022-09-15T18:05:01.960Z
2022-09-15T18:05:01.960Z
Joshua Grochow
<p>Here is an older paper you might find helpful: Logspace Machines with Multiple Oracle Tapes by <a href="http://people.csail.mit.edu/lynch/" rel="nofollow noreferrer">Nancy Lynch at MIT</a> (<a href="http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf" rel="nofollow noreferrer">PDF</a>). In particular Theorem 2.2, on PDF-page 5, might be the type of thing you're looking for. There's also a section on hierarchies defined by different numbers of oracle tapes per machine.</p>

<p>Disclaimer after the fact: Looks like a similar question and (even more similar) answer were given <a href="https://cstheory.stackexchange.com/questions/7/space-bounded-tms-and-oracles">here</a>.</p>

CC BY-SA 2.5
2010-08-19T04:33:01.467Z
2010-08-19T04:33:01.467Z
2017-04-13T12:32:28.167Z
Daniel Apon
<p>Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a good paper or thesis which provides an overview of what is known about such machines? In particular I am interested in P with multiple oracles.</p>

CC BY-SA 2.5
2010-08-18T23:37:30.967Z
just for curiosity, does having multiple oracles add more computational power with respect to a single oracle machine? It seems to me that no, because you just take the oracle corresponding to the language in the highest complexity class. Also, having a fixed number of oracles will slowdown the machine by a constant.
Marcos Villagra
CC BY-SA 2.5
2010-08-19T04:22:15.517Z
I'm with Marcos's comment about the strongest oracle subsuming the others.. but I'm interested what you had in mind now!
Daniel Apon
CC BY-SA 2.5
2010-08-19T13:08:21.427Z
Are you thinking of allowing infinitely many oracles, where the TM is allowed to choose which oracle to query?  With such a setup there might be an interesting difference between a set of oracles in which each was strictly weaker than some other oracle Q, and Q itself.
András Salamon
CC BY-SA 2.5
2010-08-19T15:18:58.593Z
Marcos and Daniel: You seem to be assuming that one oracle must contain the other. It is quite possible that they be chosen for two different problems such that neither one contains the other.

András: I had been thinking only of finite sets initially, but infinite sets of oracles may also be interesting.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-18T16:56:57.700Z
If you only want a finite number N of oracles, you could define an N-in-1 compound oracle by using the first log(N) bits of the compound oracle to indicate which suboracle you wish to query. Am I missing something?
Niel de Beaudrap
CC BY-SA 2.5
2010-08-18T17:14:44.583Z
Yes, I had thought of that. However, I am interested in specific sets of oracles, and so it seems more natural to consider them separately than as a compound object. I thought perhaps there might be some nice results in this direction.
Joe Fitzsimons
<oracles><turing-machines>
Is there a definitive reference for Turing machines with multiple oracle tapes?
Joe Fitzsimons
# Is there a definitive reference for Turing machines with multiple oracle tapes?

(Asked by: username_0 on 2010-08-18)

Most of the literature seems to be concerned with machines with single oracles for specific problems, however there appear to be a few papers that consider machines with multiple oracles. Is there a good paper or thesis which provides an overview of what is known about such machines? In particular I am interested in P with multiple oracles.

**Tags:** oracles, turing-machines

> **Comments:**
> **username_4**: If you only want a finite number N of oracles, you could define an N-in-1 compound oracle by using the first log(N) bits of the compound oracle to indicate which suboracle you wish to query. Am I missing something?  
> **username_0**: Yes, I had thought of that. However, I am interested in specific sets of oracles, and so it seems more natural to consider them separately than as a compound object. I thought perhaps there might be some nice results in this direction.  
> **username_1**: just for curiosity, does having multiple oracles add more computational power with respect to a single oracle machine? It seems to me that no, because you just take the oracle corresponding to the language in the highest complexity class. Also, having a fixed number of oracles will slowdown the machine by a constant.  
> **username_2**: I'm with Marcos's comment about the strongest oracle subsuming the others.. but I'm interested what you had in mind now!  
> **username_3**: Are you thinking of allowing infinitely many oracles, where the TM is allowed to choose which oracle to query?  With such a setup there might be an interesting difference between a set of oracles in which each was strictly weaker than some other oracle Q, and Q itself.  
> **username_0**: Marcos and Daniel: You seem to be assuming that one oracle must contain the other. It is quite possible that they be chosen for two different problems such that neither one contains the other.  András: I had been thinking only of finite sets initially, but infinite sets of oracles may also be interesting.  

---

## 2 answers

### Answer by username_5 on 2010-08-19. Score: 5 | Accepted answer

Here is a more recent paper giving a difference between single vs. multiple oracles motivated by cryptography:

Donald Beaver and Joan Feigenbaum. [Hiding instances in multioracle queries](https://doi.org/10.1007/3-540-52282-4_30). STACS 1990. Springer Lecture Notes in Computer Science, 1990, Volume 415/1990, 37-48, DOI: 10.1007/3-540-52282-4\_30

> **Comments:**
> **username_6**: just a question, i take it that the concept of multi-oracle only makes sense if the oracles cannot be collapsed into each other for some (perceived?) security reasons?  

---

### Answer by username_2 on 2010-08-19. Score: 3

Here is an older paper you might find helpful: Logspace Machines with Multiple Oracle Tapes by [Nancy Lynch at MIT](http://people.csail.mit.edu/lynch/) ([PDF](http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf)). In particular Theorem 2.2, on PDF-page 5, might be the type of thing you're looking for. There's also a section on hierarchies defined by different numbers of oracle tapes per machine.

Disclaimer after the fact: Looks like a similar question and (even more similar) answer were given [here](https://cstheory.stackexchange.com/questions/7/space-bounded-tms-and-oracles).


---

