13
$\begingroup$

Apologies if my question seems overly naive, but I haven't seen/heard/read any good answers.

What is modern computability theory "really" about? The study of feasible(even remotely feasible) algorithms falls under the domain of theoretical and non-theoretical computer science. There is, of course, the a posteriori fact that computability theory tells us a lot about the structure of the natural numbers(I'm thinking of Turing degrees, etc). But, from a certain perspective, this can be seen as a historical coincidence. (I'm not saying that this is necessarily a "correct" perspective).

So what is the motivation for the subject of modern computability theory?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ It depends on your idea of what constitutes "modern computatbility theory". Do you want quantum computing, transfinite computation, abstract recursion theory? Or perhaps notions on how to use degrees of randomness in computation (or in logic)? You might expand upon your own ideas before soliciting those of others. Gerhard "Ask Me About System Design" Paseman, 2011.04.06 $\endgroup$
    – Gerhard Paseman
    Commented Apr 6, 2011 at 20:45
  • 13
    $\begingroup$ "What would I need a computer for? All I care about is non-computable!" -- a joke told to me by a computability theorist. $\endgroup$
    – François G. Dorais
    Commented Apr 6, 2011 at 23:52
  • $\begingroup$ Thank you Gerhard, Carl, and Jason for providing me with some things to think about. (And Francois Dorais also for the joke!) My initial studies in this area were interesting, but I found it hard to see the bigger picture, as nobody at my institution is active in this subject and(again, I hope that this does not come across as too naive) it seems that this area is very "spread out" for its size(in terms of researchers, institutions, places to get an overview, etc), even compared to areas like, say, model theory. I will wait to see if any more answers come in, but thanks again. $\endgroup$
    – Michelle B
    Commented Apr 7, 2011 at 17:48

4 Answers 4

Reset to default
17
$\begingroup$

I think it's important to take a historical perspective. There was a time not so long ago when computers as we know them now did not exist. At that stage, coming up with a precise definition of an algorithm or of a Turing machine was a major advance, allowing one to build the earliest modern computers and begin the revolution that we take for granted today.

As actual computers became more powerful, interest shifted from the computable/uncomputable boundary to the feasible/infeasible boundary, where initially the definition of "feasible" was (roughly speaking) "polynomial time." So then we get the P = NP question and the birth of computational complexity theory as we know it today.

As computers became more powerful and more diverse, interest again shifted. People today are increasingly interested in parallel/distributed algorithms, cloud computing, SIMD architectures, etc. Datasets are so large that polynomial time doesn't cut it any more; people want linear time or even sublinear time algorithms.

So at the time of its invention, computability theory was about practical algorithms. The same goes for computational complexity theory and other subjects in computer science. But as technology advances, the definition of "practical" changes, so that the classical subjects no longer line up so nicely with the interests of current practitioners. That doesn't mean that the classical subjects are no longer of interest, because fundamentally important mathematical concepts never go away. But they become more abstract, and it takes a broad perspective to see their motivation and to be able to tell which problems are still of importance today. For example, in my opinion, some of the most exciting developments in computability theory today are its unexpected connections with differential geometry, as for example described in this paper by Soare. This work is very far removed from "practical algorithms" but illustrates how the study of fundamental mathematical concepts can reap unexpected dividends and is therefore worth pursuing even if immediate applications are not visible.

Improve this answer
$\endgroup$
9
$\begingroup$

What is any large branch of mathematics "really" about? In one sense the question is overly naive if it assumes all computability theorists are motivated by the same thing. Any large branch of mathematics must have numerous specialized areas of study, and several different motivations, if it is going to support a large research community. With that said, the list of topics for the CIE 2010 conference at [1] is so long that it's natural to be confused about what the topic actually is.

There are a few threads that go across most of computability theory:

  • The idea of an effective procedure. Intuitively, some operations can be done effectively and some cannot. But this can be made precise in many ways. For computability on natural numbers, we have a good consensus that Turing computability is the right notion when there are no feasibility constraints. But, for example, we have no similar consensus for computability of functions from the reals to the reals, and there is a lot of work to do there. Many of the topics of the CIE conference relate to different models of computation, ranging from automata theory to quantum computing to admissible sets.

  • The computational content of ordinary mathematics. This includes both work on things that are computable and classification of things that are not computable. There are areas that directly study mathematical principles, such as computable analysis and computable algebra, but computable model theory and effective descriptive set theory also relate to this aspect of computability theory.

  • The relationship between computability and definability. The most famous result along these lines is Post's theorem for classical computability. But there are subtle ways in which computability acts as a different kind of "definability" that doesn't fit into the usual model-theoretic framework. One specific example: there is a strong relationship between the topics of "PA degrees", "Weak König's Lemma", and the "lesser limited principle of omniscience (LLPO)". The first of these is from classical computability theory, the second is from reverse mathematics, and the third is from constructivism. Numerous results interrelate these three topics, and from the right perspective they all correspond to a certain level of a generalized "definability" hierarchy. Another way of saying it is that they give three different viewpoints of the same uncomputability phenomenon, although none of them captures it completely.

1: http://www.cie2010.uac.pt/contents/topics.html

Improve this answer
$\endgroup$
2
$\begingroup$

A somewhat analogous question can be asked about large cardinals. Specifically, why should we study large cardinals when (a) ZFC cannot prove their consistency and (b) we don't generally appeal to the existence of such large infinities when working in the rest of mathematics. However, when Vitali shows that (when assuming choice) we cannot extend the Lebesgue measure to a countably additive translation-invariant measure that measures all subsets of the Real numbers, it is natural to ask for a weakening of this property. Specifically, can we extend the Lebesgue measure in such a way if we remove the translation-invariance condition? But upon the exploration of this question, we begin to reveal this beautiful large cardinal hierarchy that provides insight on the structure of our universe of set theory. The large cardinal hierarchy then becomes an abstract object to study in its own right.

Similarly, after Church and Turing prove the existence of noncomputable sets building on the work of Gödel, one may be inclined to ask about relative computability. What if I had access to the membership in that halting set; what functions wouldn't be computable then? Alternatively, one may ask, as Post did, whether it is possible to have access to an "intermediate" noncomputable set $A$ that does not make the halting set relatively computable using $A$ as an oracle. Questions such as these help prompt the beginnings of the study of Turing degrees, and the pursuit of their answers lead to a better understanding of the arithmetical hierarchy, as you mention. This helps to make the study of computability theory self-perpetuating: not only is it of intrinsic interest, but it also helps us better understand ideas from related fields using different approaches. For a more specific example, at the very low level of the Turing degree lattice, the question of whether a function is computable has produced unifying theories of randomness, e.g., Kolmogorov Complexity and Martin-Löf randomness tests.

But let me conclude by mentioning that questions regarding oracle-assisted computations are not necessarily hypothetical. There have been theoretical physical models proposed for supertask computations that would allow us to prove all theorems of arithmetic or solve the halting problem.

Improve this answer
$\endgroup$
1
2
$\begingroup$

The main motivation is Church's thesis: a subset of $\mathbb N$ is computable (using an idealized computer, mechanical device or diligent clerk) if and only if computable by a Turing machine.

Being feasible is vague - a linear time algorithm is probably not feasible if the best constant is very large.

Being computable is more canonical: a set is computable if you could in principle find out what numbers are in the set, given enough time and space.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .