I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that

Our axiomatization has its limit: it cannot prove any results in computability theory that fail to relativize to oracle computations. This is so because the theory can be interpreted in a variant of the effective topos built from partial recursive functions with access to an oracle.

This made me wonder about non-relativizing results in computability. All results I know from computability theory do relativize to computation with oracles.

Are there results in computability theory that do not relativize? I.e. results which hold for computability but do not hold for computability relative to some oracle?

By result I mean a known theorem in computability theory, not some cooked up statement. If the notion of relativization doesn't make sense for the result then it is not what I am looking for.

It is also interesting to know if the result can be stated in the language of Synthetic Computability Theory or not.

  • 12
    $\begingroup$ Everyone knows about non-relativizing results in complexity theory like IP=PSPACE. I am asking about non-relativizing computability theory resuts, not complexity theory results. $\endgroup$ – Anonymous Jan 25 '16 at 17:58
  • 4
    $\begingroup$ @Erfan: Your comments are not relevant to the question. My question is about computability theory, you are talking about complexity theory. I am looking for non-reletivizing results, the time hierachy theorem does relativize. If you have a question about the time hierarchy theorem and relativization you can post a separate question. $\endgroup$ – Anonymous Jan 25 '16 at 20:29
  • 5
    $\begingroup$ Relevant stuff: the Homogeneity conjecture formulated by H. Rogers has been refuted in Richard A. Shore; The homogeneity conjecture (1979): there exists a Turing degree $\mathbf{a}$ such that $\mathcal{D}(\geq \mathbf{a})$ is not isomorphic to $\mathcal{D}$ (the structure of Turing degrees with partial order $\leq_{T} $). See a similar question on lo.logic $\endgroup$ – Marzio De Biasi Jan 26 '16 at 10:50
  • 3
    $\begingroup$ Good question :-) $\endgroup$ – Andrej Bauer Jan 26 '16 at 22:18
  • 2
    $\begingroup$ @Marzio: Interesting. "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_Tx$ for some $x$ (and of course, working in the Turing degrees $\geq_Tx$ is equivalent to giving all Turing machines access to $x$ as an oracle). Hence, the proof that $\varphi$ is true can't be relativized to $x$." But $\varphi$ is not really a result in computability theory, it is cooked up for a meta theorem. $\endgroup$ – Anonymous Jan 27 '16 at 4:22

Higman's Embedding Theorem: The finitely generated computably presented groups are precisely the finitely generated subgroups of finitely presented groups. Furthermore, every computably presented group (even ones countably generated) is a subgroup of a finitely presented group.

Note that this statement could relativize to: "The $O$-computably presented groups (with some oracle $O$) are precisely the finitely generated subgroups of finitely presented groups," but it does not, as one can prove that for some uncomputable $O$ there are $O$-computably presented groups that are not computably presented.

Indeed, I think any non-relativizing result of computability theory must have something of this flavor, as some part of the result or its proof must somehow "nail down" true computability from computability with an oracle $O$. In this case, it is the finiteness which nails down "actual computability." Note that, as Scott Aaronson asked for, this result is invariant to any of the usual models of computation (Turing machine, RAM, etc), but does not relativize (again, because all of the usual models of "actual" computation share some common "finiteness property").

On the other hand, one might argue that this "doesn't count" for this question, as it is more akin to a definition of computability using groups than it is a "result of computability theory." On the other other hand, it is a definition of computability that is robust to model yet that doesn't relativize. (In contrast to, say, Kleene's characterization of the computable functions which easily relativizes, by simply adding the characteristic function of your oracle to the generating set of functions. There seems to be no analogous operation for groups in the context of Higman Embedding.)

  • $\begingroup$ Is it finiteness (vs. infinity) that distinguishes your example, or countability (vs. uncountability)? $\endgroup$ – András Salamon Mar 27 '17 at 11:58
  • 2
    $\begingroup$ Excuse my ignorance, but is Higman's theorem uniform? I.e., given a computably presented group, can we uniformly compute a finitely generated group that contains it? $\endgroup$ – Andrej Bauer Mar 27 '17 at 13:26
  • 2
    $\begingroup$ Ooops, please replace "finitely generated" by "finitely presented" in my question. That was a trivial error. What I am wondering about is whether we can replace "finitely presented" with something a bit more general. $\endgroup$ – Andrej Bauer Mar 27 '17 at 14:06
  • 1
    $\begingroup$ @AndrewMorgan: I agree with the start of your argument but disagree with your conclusion. It is often quite useful that $SAT^O$ is $NP^O$-complete. I don't think of the relativization of Cook-Levin as at all unnatural... I like Andrej's suggestion very much and we'll think about it... $\endgroup$ – Joshua Grochow Mar 28 '17 at 18:38
  • 1
    $\begingroup$ @AndrewMorgan: Agreed. I would think that knot genus would be a good candidate :). $\endgroup$ – Joshua Grochow Mar 28 '17 at 19:47

This is something I've often wondered about as well!

If by "results in computability theory," you mean results that are invariant with respect to the choice of machine model (Turing machines, RAM machines, etc.), then I don't know a single example of such a result, and I definitely would've remembered if I'd seen one.

The closest I can suggest to an answer is: I think there are many interesting questions in computability theory that might depend on the machine model. For example: is the Busy Beaver function, with its usual definition in terms of Turing machines, infinitely often odd? Is the value of BB(20) independent of ZFC? Whatever the answers to these questions are, they could surely be different for relativized analogues of the BB function.


Here's a more or less trivial example: Consider the halting problem for Turing machines that are specifically prohibited (by the definition of the computation model) from accessing an oracle. It is undecidable relative both to no oracle and to a trivial oracle, and yet it is decidable relative to an oracle for the halting problem. (The problem itself doesn't change relative to an oracle because it can't access the oracle, but the (unrestricted) TM that decides the problem becomes more powerful given the oracle.)

There are plenty of other examples, too. Just play with the computation model a little and you can find other similar results.

  • 2
    $\begingroup$ Just curious: what exactly is wrong with this answer? Perhaps the downvoters do not believe that it is possible to prohibit a Turing machine from accessing an oracle and require further explanation of this? $\endgroup$ – Philip White Jan 26 '16 at 23:16
  • 6
    $\begingroup$ It doesn't seem like a very fair definition of relativization to allow the machine to have an oracle but then not allow it to use the oracle. $\endgroup$ – David Eppstein Jan 27 '16 at 1:03
  • 2
    $\begingroup$ Interesting though not what I am looking for. I am looking for a known result in computability theory that does not relativize, not an argument for how to cook up such a result. $\endgroup$ – Anonymous Jan 27 '16 at 4:13
  • 2
    $\begingroup$ Consider the following statement: H (halting problem for Turing machines without oracles) is not computable. On the other hand H is computable relative to a halting problem oracle. Even if we consider this as a way of relativizing the statement it is not an interesting one. Probably there is a similar way to relativize any statement that makes it false. A relativization is not just attaching an oracle somewhere. A relativization is interesting when it preserve some interesting class of arguments, so if a statement does not relativize we know that class of arguments can not prove the statement. $\endgroup$ – Kaveh Jan 27 '16 at 20:10
  • 2
    $\begingroup$ Take e.g the relativization method in BGS. It is interesting because it preserves simple diagonalization arguments so they cannot settle P vs. NP. If a relativization does not preserve such arguments then it is probably not an interesting way of relativizing statements. A good relativization should persevere as much of known arguments and proven results as possible, the less it preserves the less interesting it becomes. $\endgroup$ – Kaveh Jan 27 '16 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.