<p>Suppose I have an oracle X.  Then let Y be an oracle which will answer any computable question about X.  In other words, Y takes as input a Turing program which can in turn make calls to X.  Y then returns the output of that program (assuming the output is one bit, otherwise, or if the program doesn't halt, then the definition is open to interpretation).</p>

<p>Has this concept been studied?  Is there a name for such oracles?</p>

<p>This relates to communication complexity.  In that case X would be Alice's input, X' would be Bob's input, and Y and Y' would be sufficient to efficiently compute their strategies.  The Y and Y' oracles are a way to express the fact that in communication complexity one usually doesn't care how much time the parties spend on computation.</p>

CC BY-SA 3.0
2012-07-02T18:47:21.007Z
I think we can easily simulate algorithms in this oracle setting within the usual oracle setting, can't we?
Kaveh
CC BY-SA 3.0
2012-07-02T18:59:05.013Z
@Kaveh, could you explain your comment?  Having the oracle Y is more powerful than X, and in fact allows answering any question about X in one step.  However, having oracles Y and Y', derived from X and X', does not answer all questions about the pair (X, X') in a small number of calls to Y and Y'.  So I think the concept is nontrivial.  Actually it more or less is very similar to communication complexity, but by defining the oracles Y and Y', I hope to study computation without reference to communication.
Dan Stahlke
CC BY-SA 3.0
2012-07-03T02:54:01.293Z
can't we think of Y(X) as a single oracle?
Kaveh
CC BY-SA 3.0
2012-07-03T02:54:12.353Z
btw, I am not sure I understand the question correctly. In computational problems we typically have inputs and want to compute the value of a fixed function on those inputs.
Kaveh
CC BY-SA 3.0
2012-07-03T12:07:04.740Z
@Kaveh, yeah, so I was thinking of X and X' as being the inputs.  So the inputs, which are typically exponentially large, are given in the form of oracles (like in Grover's algorithm).  Then I want the oracles Y and Y' to easily answer any question that involves only one of the inputs X and X'.  It is very likely that I didn't describe it well or used the wrong language since I am just getting started in CS theory.
Dan Stahlke
CC BY-SA 3.0
2012-07-04T01:27:41.947Z
If I understand correctly, here is the setting: we have two inputs X and X' and we want to compute a function on them. The machine is given access to two fixed oracles which answer questions about X and X'. Btw, you still cannot ask any question about X and X' since the machine has to be able to write the question (i.e. the code of the TM) and that will take time. (Also what can be done will depend on the particular encoding of the TMs used by Y and Y'.)
Kaveh
CC BY-SA 3.0
2012-07-04T13:34:32.047Z
[Type-2 complexity theory](http://cstheory.stackexchange.com/questions/8516/complexity-theory-when-an-oracle-is-part-of-the-input)?
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-04T17:08:02.683Z
@Kaveh: yes, that is exactly how I am thinking of it.  The specifics depend on how everything is defined, but I would be happy to see references to anything of this general character.
Dan Stahlke
CC BY-SA 3.0
2012-07-04T17:08:14.430Z
@TsuyoshiIto: what you link to describes how I am thinking of oracle X.  But is there name for the oracle Y(X)?
Dan Stahlke
CC BY-SA 3.0
2012-07-04T18:29:01.247Z
No, “type-2 complexity theory” is not a name for an oracle.
Tsuyoshi Ito
<reference-request><computability><oracles>
Oracle that will provide any computable information about another oracle
Dan Stahlke
# Oracle that will provide any computable information about another oracle

(Asked by: username_0 on 2012-07-02)

Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then returns the output of that program (assuming the output is one bit, otherwise, or if the program doesn't halt, then the definition is open to interpretation).

Has this concept been studied? Is there a name for such oracles?

This relates to communication complexity. In that case X would be Alice's input, X' would be Bob's input, and Y and Y' would be sufficient to efficiently compute their strategies. The Y and Y' oracles are a way to express the fact that in communication complexity one usually doesn't care how much time the parties spend on computation.

**Tags:** reference-request, computability, oracles

> **Comments:**
> **username_1**: I think we can easily simulate algorithms in this oracle setting within the usual oracle setting, can't we?  
> **username_0**: @username_1, could you explain your comment?  Having the oracle Y is more powerful than X, and in fact allows answering any question about X in one step.  However, having oracles Y and Y', derived from X and X', does not answer all questions about the pair (X, X') in a small number of calls to Y and Y'.  So I think the concept is nontrivial.  Actually it more or less is very similar to communication complexity, but by defining the oracles Y and Y', I hope to study computation without reference to communication.  
> **username_1**: can't we think of Y(X) as a single oracle?  
> **username_1**: btw, I am not sure I understand the question correctly. In computational problems we typically have inputs and want to compute the value of a fixed function on those inputs.  
> **username_0**: @username_1, yeah, so I was thinking of X and X' as being the inputs.  So the inputs, which are typically exponentially large, are given in the form of oracles (like in Grover's algorithm).  Then I want the oracles Y and Y' to easily answer any question that involves only one of the inputs X and X'.  It is very likely that I didn't describe it well or used the wrong language since I am just getting started in CS theory.  
> **username_1**: If I understand correctly, here is the setting: we have two inputs X and X' and we want to compute a function on them. The machine is given access to two fixed oracles which answer questions about X and X'. Btw, you still cannot ask any question about X and X' since the machine has to be able to write the question (i.e. the code of the TM) and that will take time. (Also what can be done will depend on the particular encoding of the TMs used by Y and Y'.)  
> **username_2**: [Type-2 complexity theory](http://cstheory.stackexchange.com/questions/8516/complexity-theory-when-an-oracle-is-part-of-the-input)?  
> **username_0**: @username_1: yes, that is exactly how I am thinking of it.  The specifics depend on how everything is defined, but I would be happy to see references to anything of this general character.  
> **username_0**: @TsuyoshiIto: what you link to describes how I am thinking of oracle X.  But is there name for the oracle Y(X)?  
> **username_2**: No, “type-2 complexity theory” is not a name for an oracle.  

---

## 0 answers

