Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Is it known if there are two classes of languages $A$ and $B$ such that:
$A$ and $B$ are defined wrt the exact same type of machine (e.g. 1-tape Deterministic Turing Machines, 2-tape Deterministic Turing Machines, 1-tape Nondeterministic Turing Machines, etc);
neither $A$ or $B$ are defined wrt a restriction on space usage;
$A = B$;
there is an oracle $O$ for which $A^O \neq B^O$?
While the other answer answers the question as posed (at least, given your definition of 'type of machine'), I still think the question is rather ill-posed and that resolving this is a solution as well.
First of all, as @D.W. mentioned in the comments, the claim 'Language class $X$ is defined w.r.t. machine $M$' is ill-posed. There is no need to define a class of languages with a machine at all. Even if we have a language which is commonly described w.r.t. some machine, such as $P$, there is nothing preventing us to give an equivalent definition that uses no machine at all! (Not sure if this is doable or has been done. Perhaps you can do something based on $\lambda$-calculus?)
The second problem is that oracle access is not a modifier/property of a language class! This follows immediately from the previous point: if I define a language without using a machine, how on earth am I able to use this oracle if I don't even have a machine?
The crucial mistake that leads to your problem is that a 'language' under oracle access actually depends on the definition of the language and a 'language' with oracle access is not invariant under the method you use to define the language. In fact, the often posed statement $P^O = NP^O$ is an example of really bad notation, as $P$ and $NP$ aren't actually languages here, but methods to define languages!
Let's make this precise: Let $\mathcal{X}$ be a 'definition method' for languages that can access oracles (for example, a set of machines and some acceptance rules) Let $L(\mathcal{X})$ be the language class that is defined by $\mathcal{X}$. Let $\mathcal{X}^O$ be the extension of $\mathcal{X}$ with access to the oracle $O$.
Your question can now be rephrased as follows, let language classes $A$, $B$ such that:
- There exists an $\mathcal{X},\mathcal{Y}$ such that $A= L(\mathcal{X})$, $B = L(\mathcal{Y})$ and $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type'.
- $\mathcal{X}$ and $\mathcal{Y}$ are able to use unbounded space.
- $A=B$
- There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$
By combining 3 and 1, we can do without $A$, $B$ and focus on the machines:
- $\mathcal{X}$ and $\mathcal{Y}$ are 'of the same type' and are able to use unbounded space.
- There exists an oracle $O$ such that $L(\mathcal{X}^O) \neq L(\mathcal{Y}^O)$
Now, the question crucially depends on what 'the same type' means. If $\mathcal{X} = \mathcal{Y}$, then satisfying both 1 and 2 becomes impossible, as we now do have $\mathcal{X}^O = \mathcal{Y}^O$, so $L(\mathcal{X}^O) = L(\mathcal{Y}^O)$.
So, a necessary condition for statements 1 and 2 is the claim:
There exists an oracle $O$ such that $\mathcal{X}^O \neq \mathcal{Y}^O$.
You can define 'type' however you wish, but if two machines don't behave the same when I give them the same oracle, I don't consider those machines to be of the same type.
So, in conclusion, after rephrasing your question more formally and giving a property which I believe 'type' should adhere to, the answer to your question is actually no.
