# Limited oracle TM

Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/reject according to its answer.

Now, we add the next limitation: given an input of length $n$, the queries' length can be at most $n-1$. Now, how does the fact that this TM with oracle to $B$ can decide $B$ in polynomial time imply that $B$ is in PSPACE?

From the definition we can check whether $0$ and 1 (or the empty word if you want)are in $B$ without any oracle access. So we do so and now construct a new Turing machine to decide $B$. We simulate the special machine for $B$ on our input. When it makes an oracle access to $B$ we intercept it (it is of size smaller then our input’s size) and now run another copy of the special Turing machine on this oracle. Finally we work with at most $n$ queries at each time for each size from $n$ to $1$. It can be observed that when we get to a query of size $1$ we can answer immediately and return to the left of the tape. As we won’t work with two oracle queries of the same size simultaneously it is actually a $\mathbf{PSPACE}$ machine. Moreover, we do not save any oracle answer we compute it each time it is asked - on the fly.
• What do you mean by "we work with at most $n$ queries for each size from $n$ to 1"? Dec 14 '17 at 15:58