MAMLS (Mid-Atlantic Mathematical Logic Seminar)
  Funded by the National Science Foundation
  Hofstra University, Hempstead, Long Island, NY
  March 6, 2004

Invited Speaker: 

  Stephen G. Simpson
  Pennsylvania State University

Title: Two topics in the theory of computability and unsolvability


  (1) Almost everywhere domination.

  This is joint work with Natasha Dobrinen.  A Turing degree is said
  to be almost everywhere dominating if it contains functions which
  dominate all functions that are computable from a random Turing
  oracle.  We consider the problem of characterizing the Turing
  degrees which are almost everywhere dominating.  We relate this to
  some questions in the reverse mathematics of measure theory.

  (2) An extension of the recursively enumerable Turing degrees.

  The semilattice of r. e. Turing degrees has been studied intensively
  for almost 50 years, yet no natural examples of r. e. Turing degrees
  are known beyond the two originally noted by Turing: 0 = the degree
  of solvable problems, and 0' = the degree of the Halting Problem.
  In order to overcome this obstacle, we present a natural embedding
  of the r. e. Turing degrees into the Muchnik degrees of mass
  problems given by nonempty Pi^0_1 subsets of 2^omega.  We exhibit
  some natural examples of such degrees, and we present a result due
  to Stephen Binns showing that the lattice of all such degrees is
  well behaved.