MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

closed as too broad by Andrés E. Caicedo, Andy Putman, Steven Landsburg, Peter LeFanu Lumsdaine, Andrej Bauer Feb 15 '14 at 6:51

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

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. – Noah Schweber Feb 14 '14 at 20:31
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. – Andy Putman Feb 14 '14 at 21:49
@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. – Peter LeFanu Lumsdaine Feb 15 '14 at 0:15
"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. – Carl Mummert Feb 15 '14 at 1:39
This is not research-level. It is like asking "what are some real-life applications of PDE's?" I am nailing the last nail on the coffin. – Andrej Bauer Feb 15 '14 at 6:53
up vote 14 down vote accepted

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 where more routinely published in Annals of Mathematics.

share|cite|improve this answer
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). – Joshua Grochow Feb 14 '14 at 23:15
@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... – François G. Dorais Feb 14 '14 at 23:24
@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? – Joshua Grochow Feb 14 '14 at 23:25
@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. – François G. Dorais Feb 14 '14 at 23:37

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.; also 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.

share|cite|improve this answer
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? – HJRW Feb 14 '14 at 22:08
@HJRW: After I saw it, I was actually expecting you to give a (group theory focused) answer to this question! – François G. Dorais Feb 14 '14 at 23:26
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? – Noah Schweber Feb 15 '14 at 15:00