9
$\begingroup$

In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this?

Edit: Given that we cannot explicitly and mechanically understand the non-computable, what traces of non-computability (nonzero Turing degree) might we encounter in everyday life on Earth?

$\endgroup$
8
  • 9
    $\begingroup$ I disagree with the votes to close this question; I think more work could have been put into asking it, but I also think it's definitely appropriate for MO. $\endgroup$ Commented Feb 14, 2014 at 20:31
  • 15
    $\begingroup$ I voted to close because it is a lazy and poorly thought out question (and the OP has flooded the site with multiple such questions today). If you like it enough to keep it open, edit it to make it a good question. $\endgroup$ Commented Feb 14, 2014 at 21:49
  • 4
    $\begingroup$ @Noah: besides Andy Putman's reasons, I voted to close because "in real life" is extremely broad and subjective, and rarely leads to interesting content. And, indeed, the contentful parts of the answers so far are those that explicitly drop the "in real life" part of the question. $\endgroup$ Commented Feb 15, 2014 at 0:15
  • 2
    $\begingroup$ "No, there are absolutely no practical applications; the entire field is simply a waste of time by sheltered academics." I am not voting to close because of the comments by @Noah S, but I think this question falls into the "subjective and argumentative" close reason. $\endgroup$ Commented Feb 15, 2014 at 1:39
  • 2
    $\begingroup$ I don't see the issue. To me, it's an interesting and reasonable question. No further explanation or background is needed to get the point of the question across (not saying more would hurt). And I would hope that saying something has no practical applications is merely an observation rather than a value judgement. $\endgroup$
    – usul
    Commented Feb 15, 2014 at 2:13

2 Answers 2

19
$\begingroup$

Application to everyday life

Any time you watch the "spinning beach ball" or "hour glass" on your computer, trying to decide whether it's time to reboot or just wait a little longer, you are doing something like trying to decide the Halting Problem which has Turing degree $\mathbf 0'$.

On the other hand, calculating the bill and the tip at a restaurant has Turing degree $\mathbf 0$.

Application to physics

Random sequences (almost all sequences) have Turing degree incomparable with $\mathbf 0'$.

Imagine that you conduct a "Schrödinger's Cat" type experiment repeatedly, in fact infinitely many times. Supposedly the resulting sequence of dead/alive or 0/1 bits will be random. But how random? Turing degree theory allows for a classification: will the sequence be Martin-Löf random relative to $\mathbf 0'$? Relative to $\mathbf 0''$? Relative to all reals that are first order definable in the language of set theory? What does it really mean to say that at the fundamental level, the physical world is random (i.e., follows a probability distribution)?

On the other hand, apart from collapse-of-the-wave-function phenomena, it seems that the physical world is deterministic and even computable, i.e. Turing degree $\mathbf 0$. Is this really the case, or is the appearance just a consequence of our limited abilities to understand anything noncomputable?

Lack of applications

All this being said, experience has shown that computational complexity ($P$, $NP$, etc.) is more practically relevant than Turing degrees in many ways. And already in 1975, Baker, Gill, and Solovay showed that the methods used in Turing degree theory and computability theory more generally, being relativizable, can never settle whether $P=NP$. It kind of seems like 1975 was a watershed moment -- before that, Turing degree papers were more routinely published in Annals of Mathematics.

$\endgroup$
5
  • 2
    $\begingroup$ Although formally true, I wouldn't say your last paragraph indicates a lack of applications of Turing degree, but should be taken more positively as a whole range of applications of a slight variant of the notion, namely of Turing p-degrees (i.e. degree under polynomial-time reducibility). $\endgroup$ Commented Feb 14, 2014 at 23:15
  • 6
    $\begingroup$ @Joshua: Gerald Sacks (who was instrumental in the development of Turing degrees) once told me something that I remember every day, namely that theorems aren't that interesting but their proofs are interesting... $\endgroup$ Commented Feb 14, 2014 at 23:24
  • $\begingroup$ @FrançoisG.Dorais: He said the same thing in a class I took from him as an undergrad. I mostly agree with that statement most of the time :). How was it related to my previous comment though? $\endgroup$ Commented Feb 14, 2014 at 23:25
  • 2
    $\begingroup$ @Joshua: From my work in reverse mathematics, I've seen over and over that techniques from computability theory have very broad appicability. Even though many haven't been applied yet, I think it's only a matter of time before more advanced techniques get applied, in some way or another, to different fields of mathematics. $\endgroup$ Commented Feb 14, 2014 at 23:37
  • $\begingroup$ It's not really true that when watching the spinning wheel on the mac and deciding what to do I'm trying to solve the Halting problem. I'm pretty convinced, after all, that if the wheel keeps spinning for an hour that I should restart the computer. $\endgroup$ Commented Nov 24 at 13:34
9
$\begingroup$

Focusing on applications to mathematics - as opposed to real life :P - let me mention two points I find interesting:

  • First, recursiveness shows up occasionally un-asked-for in classification theorems. My personal favorite example of this is Higman's Embedding Theorem, which shows that the finitely generated groups which can be embedded in a finitely presentable group are precisely the finitely generated recursively presentable groups. What makes this result interesting to me is that there is no obvious way to relativize it, leaving open the following (to me, very interesting) question: for which classes $\mathcal{D}$ of degrees is there a structural characterization of the finitely generated $\mathcal{D}$-presentable groups? (E.g., the $\Delta^0_2$-presentable groups.) Calling this an "application" is certainly a stretch, but this is one sort of area that might become interesting in the future, and I'm an optimist.

  • Second, there is recent work by Nabutovsky and Weinberger (see e.g. http://arxiv.org/pdf/math/9711225.pdf; also http://press.princeton.edu/titles/7903.html) using computability theory to study the structure of some complicated moduli spaces. Although the more heavy-duty results use computability theory in their statements, the simpler results involve no computability theory but have proofs relying on the fact that there is no algorithm for determining which "nice" smooth homology spheres are actualy spheres. I think in general, using computability theory to study moduli spaces could be an incredibly interesting future direction of research.

$\endgroup$
3
  • 6
    $\begingroup$ It seems a shame not to mention the ur-Nabutovsky--Weinberger theorem, I think actually due to Gromov, which uses the existence of groups with undecidable word problem to prove the existence of manifolds with infinitely many null-homotopic geodesics. Could there be a more surprising application of computability theory? $\endgroup$
    – HJRW
    Commented Feb 14, 2014 at 22:08
  • $\begingroup$ @HJRW: After I saw it, I was actually expecting you to give a (group theory focused) answer to this question! $\endgroup$ Commented Feb 14, 2014 at 23:26
  • 2
    $\begingroup$ HJRW: I didn't mention that because I didn't know about it - that's fascinating! Can you point me to a good source on it? $\endgroup$ Commented Feb 15, 2014 at 15:00