<p>This might not answer your question (which to be honest I don't fully understand), but I think it's in the same spirit.  It's known that there is a difference in reducibility between a logspace TM with one oracle tape, and one with access to multiple oracle tapes.  Also, the following notion of logspaceness has nice properties: the TM can only use a log-amount of space on its work tape, but it can use polynomial-amount of space on its oracle tapes.</p>

<p>Reference: <a href="http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf">http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf</a></p>

CC BY-SA 2.5
2010-08-17T02:33:48.487Z
2010-08-17T02:33:48.487Z
Aaron Sterling
<p>NSPACE(0)P=RE wich I guess is tad bit absurd.</p>

<p>Indeed, let L be a language recursively enumerable, M a TM who recognise L and M′ a TM that read an input and a number n of "1" and then simulates M for this input on n steps. Then without using any space I could copy the input on the oracle tape, guess the number of 1 needed and query M′. </p>

<p>Then, M' will accept iff M accept and have an input big enough to be polynomial.</p>

CC BY-SA 2.5
2010-08-24T18:44:15.433Z
2010-08-24T18:44:15.433Z
Arthur MILCHIOR
<p>I think one surprising fact is that in this model Savitch's theorem doesn't "obviously" relativize. That is, one can see that $PSPACE^P=EXPTIME$ and $NPSPACE^P=NEXPTIME$ in this model, and we don't currently know that $EXPTIME=NEXPTIME$ (and Savitch's theorem in this context does not seem to give it).  I'd be interested in whether this can be pushed to "provably" non-relativizing.</p>

<p>One can also observe that $NL^{NL}=NL^L=NP$ in this model.</p>

<p>However, I think that this model is at least worth thinking about, with respect to issues of relativization in the space hierarchy theorem.  Also, in some sense, I want $L^A$ to make poly-sized queries to $A$.</p>

CC BY-SA 2.5
2010-08-24T03:50:14.207Z
Do you have a reference ? I would have expected $\rm{NSPACE(0)^P=RE}$. Indeed, let $L$ be a language recursively enumerable, $M$ a TM who recognise $L$ and $M'$ a TM that read an input and a number $n$ of "1" and then simulates $M$ for this input on $n$ steps.

Then  without using any space I could copy the input on the oracle tape, guess the number of 1 needed and query $M'$.
Arthur MILCHIOR
CC BY-SA 2.5
2010-08-18T06:13:15.360Z
One thing I forgot: as NL=coNL we should want NL^NL=NL, but clearly if NL^NL=NP in this model we cannot use NL=coNL to collapse the "NL-hierachy".  In a different notion of space-bounded oracles, the hierarchy does indeed collapse (see Immerman's NL=coNL paper for references).
miforbes
CC BY-SA 2.5
2010-08-18T06:11:32.697Z
2010-08-18T06:11:32.697Z
miforbes
<p>In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).</p>

<p>Is such a construction useful? Does it yield any particularly absurd results?</p>

CC BY-SA 2.5
2010-08-16T22:54:34.097Z
If you ave a TM with a write-only Oracle tape, how do you read the answer? You can just forget about the oracle then.
Marcos Villagra
CC BY-SA 2.5
2010-08-17T02:25:49.130Z
There are delicate issues in deciding what is the right definition of oracle access for space-bounded machines. See "Relativizing Small Complexity Classes and their Theories" by Klaus Aehlig, Stephen Cook, and Phuong Nguyen, CSL 2007.
Kaveh
CC BY-SA 2.5
2010-08-17T04:32:16.560Z
@Marcos: I believe the answer is simply the resulting internal state of the machine, and is not written to the oracle tape.
Joe Fitzsimons
CC BY-SA 2.5
2010-08-18T06:13:47.277Z
What is the reference for this definition of space-bounded oracle machines?
miforbes
<cc.complexity-theory><space-bounded><oracles>
space-bounded TMs and oracles
Jeremy Hurwitz
# space-bounded TMs and oracles

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

In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).

Is such a construction useful? Does it yield any particularly absurd results?

**Tags:** cc.complexity-theory, space-bounded, oracles
> **Comments:**
> **username_1**: If you ave a TM with a write-only Oracle tape, how do you read the answer? You can just forget about the oracle then.  
> **username_2**: There are delicate issues in deciding what is the right definition of oracle access for space-bounded machines. See "Relativizing Small Complexity Classes and their Theories" by Klaus Aehlig, Stephen Cook, and Phuong Nguyen, CSL 2007.  
> **username_3**: @Marcos: I believe the answer is simply the resulting internal state of the machine, and is not written to the oracle tape.  
> **username_4**: What is the reference for this definition of space-bounded oracle machines?  

---

## 3 answers

### Answer by username_4 on 2010-08-18. Score: 10 | Accepted answer

I think one surprising fact is that in this model Savitch's theorem doesn't "obviously" relativize. That is, one can see that $PSPACE^P=EXPTIME$ and $NPSPACE^P=NEXPTIME$ in this model, and we don't currently know that $EXPTIME=NEXPTIME$ (and Savitch's theorem in this context does not seem to give it). I'd be interested in whether this can be pushed to "provably" non-relativizing.

One can also observe that $NL^{NL}=NL^L=NP$ in this model.

However, I think that this model is at least worth thinking about, with respect to issues of relativization in the space hierarchy theorem. Also, in some sense, I want $L^A$ to make poly-sized queries to $A$.

> **Comments:**
> **username_4**: One thing I forgot: as NL=coNL we should want NL^NL=NL, but clearly if NL^NL=NP in this model we cannot use NL=coNL to collapse the "NL-hierachy".  In a different notion of space-bounded oracles, the hierarchy does indeed collapse (see Immerman's NL=coNL paper for references).  
> **username_6**: Do you have a reference ? I would have expected $\rm{NSPACE(0)^P=RE}$. Indeed, let $L$ be a language recursively enumerable, $M$ a TM who recognise $L$ and $M'$ a TM that read an input and a number $n$ of "1" and then simulates $M$ for this input on $n$ steps.  Then  without using any space I could copy the input on the oracle tape, guess the number of 1 needed and query $M'$.  

---

### Answer by username_5 on 2010-08-17. Score: 9

This might not answer your question (which to be honest I don't fully understand), but I think it's in the same spirit. It's known that there is a difference in reducibility between a logspace TM with one oracle tape, and one with access to multiple oracle tapes. Also, the following notion of logspaceness has nice properties: the TM can only use a log-amount of space on its work tape, but it can use polynomial-amount of space on its oracle tapes.

Reference: <http://groups.csail.mit.edu/tds/papers/Lynch/tcs78.pdf>


---

### Answer by username_6 on 2010-08-24. Score: 3

NSPACE(0)P=RE wich I guess is tad bit absurd.

Indeed, let L be a language recursively enumerable, M a TM who recognise L and M′ a TM that read an input and a number n of "1" and then simulates M for this input on n steps. Then without using any space I could copy the input on the oracle tape, guess the number of 1 needed and query M′.

Then, M' will accept iff M accept and have an input big enough to be polynomial.


---

