I am afraid this post may show my naivety. At a recent conference, someone told me that there are some arguments in computability theory that don't relativize. Unfortunately, this person (who I think may be an MO regular) couldn't give me any examples off-hand.
My naive understanding is that one can take any proof, fix an oracle and replace "Turing machine" with "Turing machine using that oracle". (Similarly, replace "computable" with "computable w.r.t. this oracle" and so on.) But I am probably missing something.
So is it possible to relativize any proof? Is it not possible? Or is it technically possible to relativize any proof, but the relativization isn't what you may expect?
If it is not always possible, can someone provide me a good example or reference? Also, any discussion on what makes a proof relativizable or not would be of help.
Actually, while writing this, I may have come up with an example. It's known that $P=NP$ and $P \neq NP$ for different oracles. But this is a relativization of a theorem (conjecture), not it's proof. So this brings up related questions. Is relativizing the statement of a theorem different from relativizing the proof? What if the theorem/proof has nothing to do with the actual model of computation (e.g. the proof doesn't refer to ideas such as time-complexity, only computability)?
Thanks!
Best Answer
Early in the history of recursion theory, the realization that all known proofs in the subject could be relativized in the manner you indicate led Hartley Rogers to make what is called the homogeneity conjecture.
Let $\mathcal{D}$ be the structure of the Turing degrees with the partial order of Turing reducibility $\leq_T$. Let $\mathcal{D}(\geq \mathbf{x})$ be the structure of the Turing degrees that are $\geq_T \mathbf{x}$ also with the partial order $\leq_T$. The homogeneity conjecture says that for any Turing degree $\mathbf{x}$, $\mathcal{D}$ is isomorphic to $\mathcal{D}(\geq \mathbf{x})$.
Richard Shore refuted the homogeneity conjecture in an elegant 1979 paper -- it's only one page long (though it relies on earlier work coding models of arithmetic in $\mathcal{D}$). A couple years later, Harrington and Shore showed that you can do even better. Not only are there Turing degrees $\mathbf{x}$ for which $\mathcal{D}$ and $\mathcal{D}(\geq \mathbf{x})$ aren't isomorphic as structures, there are Turing degrees $\mathbf{x}$ so that $\mathcal{D}$ and $\mathcal{D}(\geq \mathbf{x})$ aren't elementarily equivalent.
So this means that there is a first order sentence $\varphi$ in the language only containing $\leq_T$ which is true about the Turing degrees, but which is false if you relativize the sentence to the Turing degrees $\geq_T \mathbf{x}$ for some $\mathbf{x}$ (and of course, working in the Turing degrees $\geq_T \mathbf{x}$ is equivalent to giving all Turing machines access to $\mathbf{x}$ as an oracle). Hence, the proof that $\varphi$ is true can't be relativized to $\mathbf{x}$.
A somewhat misleading and oversimplified explanation of why this occurs is that you can code models of arithmetic into $\mathcal{D}$ (or $\mathcal{D}(\geq \mathbf{x})$) which can then interpret unrelativized concepts like being arithmetically definable or hyperarithmetically definable.
A particularly spectacular form of this phenomenon would occur if Slaman and Woodin's biinterpertability conjecture is true. The conjecture says that the following relation (on $\overrightarrow{\mathbf{p}}$ and $\mathbf{d}$) is definable in $\mathcal{D}$: "$\overrightarrow{\mathbf{p}}$ codes a standard model of first order arithmetic and a real $X$ such that $X$ is of degree $\mathbf{d}$".
All that being said, just about every proof in recursion theory that I know of relativizes. I'd be very interested in a proof which doesn't relativize and doesn't factor through the coding machinery I've mentioned above.
By the way (and somewhat ironically), the Baker-Gill-Solovay theorem that you mentioned does itself relativize. The relativized version says that for any oracle $X$, there are oracles $A$ and $B$ so that $X$ is poly-time reducible to both $A$ and $B$, and $P^A = NP^A$ and $P^B \neq NP^B$. (We've relativized to $X$ here. The unrelativized result simply says that there are oracles $A$ and $B$ so that $P^A = NP^A$ and $P^B \neq NP^B$). Of course, the real point is that a proof that $P \neq NP$ can't use a technique that relativizes.