28
$\begingroup$

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.

$\endgroup$
  • 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
  • 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
  • 2
    $\begingroup$ @Marzio: Andrew Marks continues: "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." $\endgroup$ – Anonymous Jan 27 '16 at 4:23
11
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it finiteness (vs. infinity) that distinguishes your example, or countability (vs. uncountability)? $\endgroup$ – András Salamon Mar 27 '17 at 11:58
  • 1
    $\begingroup$ @AndrejBauer: I don't see that. Higman's proof basically goes by showing that you can simulate Kleene's basic functions and operators (see the Wikipedia page for terminology) using group constructions. If you throw in an oracle as a basic function (the natural way of relativizing Kleene's characterization) I don't see how to simulate that using a group construction. $\endgroup$ – Joshua Grochow Mar 27 '17 at 18:40
  • 1
    $\begingroup$ Well then, perhaps there should be a Grochow's theorem :-) For example, perhaps to every oracle we can assign some sort of a ($O$-computable) group $G_O$, and then the theorem will say that every $O$-computably presented group is a subgroup of a finitely presented quotient of a finite product of copies of $G_O$. Or something like that. We should use imagination, not look for reasons to avoid looking for a theorem. $\endgroup$ – Andrej Bauer Mar 27 '17 at 18:48
  • 3
    $\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
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Examples of non-relativizing statements can be found coming from degree theory (per my answer); of course, whether these are natural or not is another story. $\endgroup$ – Noah Schweber Jan 15 at 19:14
3
$\begingroup$

The short version of this answer is:

Degree theory (e.g. the study of the first-order theory of the partial order of Turing degrees) yields examples of non-relativizing statements, although these statements are of course highly technical. One useful tool for understanding this situation is the cone theorem ... which also limits the extent to which this behavior can happen.


There are indeed theorems which don't relativize, about which I'll say more below. First, though, let me observe that there is a sense in which all (reasonable) theorems eventually relativize:

(Martin's cone theorem) Suppose $A$ is a "nicely definable" property of Turing degrees. Then either every sufficiently large Turing degree has $A$ or every sufficiently large Turing degree fails $A$; precisely, there is some degree ${\bf d}$ such that for every degree ${\bf c}\ge_T{\bf d}$ we have $A({\bf c})\leftrightarrow A({\bf d})$.

"Nicely definable" here is a bit technical; specifically, we want the set of elements of $A$ (thought of as a subset of $2^\omega$) to be determined, in the sense that one player or the other has a winning strategy in the associated Gale-Stewart game. I'll briefly observe that $(i)$ every Borel set is determined, and so every property of Turing-invariant property which is expressible in the infinitary logic $\mathcal{L}_{\omega_1,\omega}$ either holds or fails on a cone, and $(ii)$ additional set-theoretic assumptions can push determinacy far beyond the Borel sets. Heuristically, one will not run into a non-determined set of Turing degrees without explicitly trying to.

The proof of the cone theorem can be boiled down to a single sentence:

Supposing $A\subseteq 2^\omega$ is Turing-invariant and determined with a winning strategy $\sigma$ for player $1$, given any $r\ge_T\sigma$ consider the play of $\sigma$ against the "silly" strategy for player $2$ which simply plays the bits of $r$ regardless of what player $1$ does.

OK, this isn't really fair: the difficult aspect of the cone theorem isn't the theorem itself but rather the determinacy results it leans on, since it's not a prior clear that determinacy is something we should expect of "nice" sets in the first place. The clearest proof of Borel determinacy I've seen is in Moschovakis' book, but it's still quite involved. Large cardinals improve things substantially - the proof of analytic determinacy from a measurable cardinal is actually much simpler than Borel determinacy from ZFC - but it's never really easy after the first couple levels of the Borel hierarchy.


Now let's talk about the positive role of the cone theorem in finding non-relativization phenomena.

First, here's an interesting application of the cone theorem to get a dubious example of what you're looking for. By the Arslanov Completeness Criterion, ${\bf 0'}$ is not PA over anything over which it is low; however, since the low basis theorem does relativize, by the cone theorem we know that for all sufficiently large degrees ${\bf a}$ there is some ${\bf b}$ such that ${\bf a'}$ is low an PA over ${\bf b}$. This apparently contradicts the fact that the proof of ACC also relativizes; the saving grace is that the required ${\bf b}$ is not in the interval $[{\bf a},{\bf a'}]$ (and indeed we get an interesting jump inversion counterexample here).

Ultimately the above indicates that we've (fine, I've) relativized the original result incorrectly here: when relativizing a degree-theoretic fact to ${\bf a}$, we should restrict attention to the upper cone $\{{\bf c}: {\bf c}\ge_T{\bf a}\}$ (that is, look at what happens if ${\bf a}$ were to be thought of as ${\bf 0}$). This suggests a natural sub-question of your question:

Is there some sentence $\varphi$ in the language of partial order such that $\mathcal{D}\models\varphi$ but $\mathcal{D}_{\ge_T{\bf a}}\models\neg\varphi$ for all sufficiently large degrees ${\bf a}$?

Here $\mathcal{D}$ (resp. $\mathcal{D}_{\ge_T{\bf a}}$) is the partial order of Turing degrees (resp. Turing degrees $\ge_T{\bf a}$) under $\ge_T$. The language of partial order may seem quite limited at first, but it's actually extremely expressive; in particular, contra early expectations it is known that $\mathcal{D}$ has a highly complicated first-order theory and at most countably many automorphisms (and it's conjectured that $\mathcal{D}$ is rigid, a proposed counterexample by Cooper being generally considered to be flawed).

  • Note that the question above treats a precise notion of (non-)relativization, which I think is rather neat! And per the expressivity of $\mathcal{D}$, it's not too restrictive either.

The answer to this sub-question turns out to be yes; this is a consequence of Theorem 3.1 of Nerode and Shore (although they don't quite phrase it this way - also, they include a symbol for the Turing jump, but it was later shown that the jump is definable from the partial order structure alone).

The proof gives such a $\varphi$, but we can also show the existence of such a $\varphi$ using their theorem as a blackbox ... via the cone theorem! Suppose no such $\varphi$ existed; then for each $\varphi\in Th(\mathcal{D})$, the set $T_\varphi=\{{\bf a}: \mathcal{D}_{\ge{\bf a}}\models\varphi\}$ contains a cone. But since the intersection of countably many cones in $\mathcal{D}$ is again a cone, we get a cone of ${\bf a}$ in $\bigcap_{\varphi\in Sent} T_\varphi$ - in other words, a cone of degrees whose upper cones are elementarily equivalent to $\mathcal{D}$, contradicting Nerode/Shore.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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
  • 9
    $\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.