# space-bounded TMs and oracles

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?

• 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 Aug 16 '10 at 22:54
• 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 Aug 17 '10 at 2:25
• @Marcos: I believe the answer is simply the resulting internal state of the machine, and is not written to the oracle tape. – Joe Fitzsimons Aug 17 '10 at 4:32
• What is the reference for this definition of space-bounded oracle machines? – miforbes Aug 18 '10 at 6:13

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$.

• 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 Aug 18 '10 at 6:13
• 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 Aug 24 '10 at 3:50

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.

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.