FOM: Applications of Computability Theory

[Stuart A. Kurtz]

Dear FOM Readers,

I am writing as an applied computability theorist regarding the
ongoing Soare/Simpson controversy.

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!                                                                         !
!   Point 1.  While computability theory originated in the study of the   !
!   foundations of mathematics, it is now a part of the foundations of    !
!   other applied fields.                                                 !
!                                                                         !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

The mathematical science of computation, founded in large part on
computability theory, overlaps the current disciplinary boundaries
of mathematics and computer science.  It is important in assessing
the utility of computability theory, even in the context of a list
on the foundations of mathematics, to keep in mind the substantial
role computability theory plays in the foundations of computer
science.

Computability has a foundational role in each of the following
areas.  This list shouldn't be taken as exhaustive -- it very much
reflects my particular interests.

a. Complexity theory, including abstract complexity, structural
   complexity, and relativization.

b. Inductive inference, i.e., computational learning theory.

c. Constructive mathematics.

d. Randomness.

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!                                                                         !
!   Point 2.  The principle technologies of modern computability theory   !
!   are used in applied settings.                                         !
!                                                                         !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

My experience as an applied computability theorist has been that
there is a fruitful exchange of ideas and technologies between
modern computability theory and theoretical computer science.  I
will cite applications of priority methods that I've made in each of
the four application areas mentioned above.  All of the following
examples involve injury.

a. Kurtz-Mahaney-Royer proved the existence of a polynomial-time
many-one degree that consists of a single polynomial-time
isomorphism type (a collapsing degree) computable in exponential
time.

b. Kurtz-Royer proved that an inductive inference machine can be
effectively transformed to another machine that learns the same
languages in extension (TxtBC), but which has the additional
property that it only makes conjectures for languages that are
learnable (is prudent).

c. Downey-Kurtz proved that there is a computable torsion-free
abelian group that is not computably linearly ordered.  This shows
that the classical theorem that every torsion-free abelian group can
be ordered is nonconstructive.

d. In my thesis, I proved that (arithmetically) random sets are
relatively c.e., i.e., the set of reals that are c.e. in a real of
strictly lower Turing degree has measure 1.

These examples do not exhaust my personal use of priority methods,
nor am I the only computer scientist who has found priority methods
useful.  While priority methods are not especially common in
complexity theory, they are no longer so rare as to be remarkable.

Before concluding, I'd like to describe one more example of a
successful technology transfer from computability theory to
complexity theory.

Priority arguments are not the only technique whereby computability
theorists produce sets with interesting computational properties.  A
half-dozen years ago, Slaman used a sophisticated forcing argument
to solve a problem in Learning Theory proposed by Gasarch.  The
beautiful thing about Slaman's technique was that it could handle
both diagonalization and coding requirements, whereas traditional
finite-extension (Cohen) forcing can only handle diagonalization
requirements.  [N.B., those who doubt the reality of the commerce of
ideas between computability and complexity theory should consider
the list of authors of "Extremes in the Degrees of Inferability,"
published in the Annals of Pure and Applied Logic in 1994: Fortnow,
Gasarch, Jain, Kinber, Kummer, Kurtz, Pleszkoch, Slaman, Stephan,
and Solovay.]

Although forcing arguments were well established in complexity
theory (e.g., Mehlorn '75 showed the set of oracles relative to
which P does not equal NP is comeager), only finite-extension
forcing had been used.  Fortnow and I were quick to grasp how
Slaman's approach could be applied to complexity theory, and
together with our students (Fenner, Li, and Rogers), adapted this
technology to obtain a number of new relativizations.  The most
significant of these was the Fenner-Fortnow-Kurtz construction of an
oracle relative to which the Berman-Hartmanis Isomorphism Conjecture
holds, solving a well-known 20-year old problem, which itself had
been inspired by analogies with Myhill's theorem from computability
theory.

Respectfully,

Stu
---------------
Stuart A. Kurtz
Professor and Chair
Department of Computer Science
The University of Chicago

web:   http://www.cs.uchicago.edu/~stuart
email: stuart at cs.uchicago.edu
phone: (773)-702-3493
fax:   (773)-702-8487