[FOM] Intermediate Turing Degrees

Stephen G Simpson simpson at math.psu.edu
Tue Aug 31 11:30:56 EDT 2010


Merlin Carl writes:

  it is well known that there's a rich structure of Turing degrees
  between 0 and 0`. However, [...] I have yet neither seen
  intermediate degrees occuring in other disciplines of mathematics
  nor corresponding to an application. [...]

Some years ago I was a principal participant in an extensive FOM
discussion of the role of intermediate r. e. Turing degrees and
priority arguments in what was then being called "applied
computability theory".  See for instance:

  http://cs.nyu.edu/pipermail/fom/1999-August/003299.html

  http://www.cs.nyu.edu/pipermail/fom/1999-August/003327.html

  http://www.cs.nyu.edu/pipermail/fom/1999-August/003331.html

  http://www.cs.nyu.edu/pipermail/fom/2005-February/008809.html

Unfortunately, although the discussion was interesting and promising
from a scientific viewpoint, it became impossible to continue on the
FOM list.  Instead I have continued the discussion in another way, by
publishing several relevant research articles:

  Mass problems and randomness (BSL, 2005)

  An extension of the recursively enumerable Turing degrees (JLMS, 2007)

  Mass problems and almost everywhere domination (MLQ, 2007)

  Some fundamental issues concerning degrees of unsolvability (CPOI II, 2008)

  Mass problems and hyperarithmeticity (JML, 2008)

  Mass problems and intuitionism (NDJFL, 2008)

  Mass problems and measure-theoretic regularity (BSL, 2009)

All of these articles are available on my web page.

----

 Name: Stephen G. Simpson

 Affiliation: Pennsylvania State University

 Research interests: foundations of mathematics, mathematical logic

 Web page: http://www.math.psu.edu/simpson/



More information about the FOM mailing list