Relativizing Space

We normally define relativization to an oracle A with a special Turing machine that has an extra tape where the machine can write down a string x and move to a special state q_? and will magically go to a state q_y if x is in A and q_n otherwise.

Scott Aaronson asked me about relativization for space classes noting the difficulty of the above definition. Does the oracle tape count as space? You want a log-space bounded machine to at least write its own input on the oracle tape but you don't want the tape to be used as auxiliary storage.

Ruzzo, Simon and Tompa developed the best model for oracle relativization. They allow a long oracle tape with the following restrictions:

• The oracle tape is one-way write only.
• A nondeterministic (or probabilistic or quantum) machine must act deterministically while writing on the oracle tape.
• Once the query is made the tape is magically erased.

In this model a log-space machine can ask polynomial-size queries but these queries can be computed in log-space from the input and an extra O(log n) bits (the configuration of the machine right before writing the oracle query).

The Ruzzo-Simon-Tompa definition works well for defining Turing reductions for space-bounded machines but not so much for relativizing theorems, for example showing that alternating polynomial-time equals polynomial space for all oracles. Jonathan Buss gave a model to handle this case but we don't really get limitations on techniques for relativization results on space classes like we do for time. Best not even to bother looking for relativized space class oracles and just think of PSPACE of alternating polynomial-time in results like there is an A such that P^A=PSPACE^A.