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
I am trying to solve a question from the exercise of this book, pg. 46,section 7.4.
Let $M$ be a deterministic Turing machine that only queries oracle strings that are shorter than the input string. Show that if $A = L(M^A)$ and $B = L(M^B)$ then $A = B$.
I think I have to apply induction. Does it involve self-reducibility concept? Just hints would be sufficient.
You can prove by induction that for all $n\in\mathbb{N}$, $A$ and $B$ agree on all the strings in $\{0,1\}^{\le n}$, i.e. $A\cap\{0,1\}^{\le n}=B\cap\{0,1\}^{\le n}$.
The case of $n=0$ follows from the fact that $M$ does not query its oracle on the input $\epsilon$, which means $M^A$ accepts $\epsilon$ iff $M^B$ accepts it. For $n>0$, let $x\in\{0,1\}^{n+1}$ be some length $n+1$ string. We need to prove (under the inductive hypothesis) that $x\in A\iff x\in B$. Suppose $x\in A$, then $M^A$ accepts $x$. Note that on input $x$, $M^A$ queries strings in $\{0,1\}^{\le n}$ alone, where $A$ and $B$ agree. This means that replacing the oracle from $A$ to $B$ won't change $M$'s outcome on $x$, hence $M^B$ accepts $x$ and therefore $x\in B$, since $B=L(M^B)$. The same arguments apply in the $x\notin A$ case, which concludes the proof.
