|
Workshop on Recursion Theory
(1 - 5 Aug 2011)
Jointly funded by the John Templeton Foundation
~ Abstracts ~
The jump of a structure
Antonio Montalban, University of Chicago, USA
In the last few years there has been various definitions of what the Turing jump of an algebraic structure should be. We will discuss the different definitions of the jump of a structure and talk about recent results in the area.
« Back... Toward deciding the AE-theory of the Sigma^0_2-enumeration degrees
Steffen Lempp, University of Wisconsin, USA
In joint work with Andrews, Ng and Sorbi, we give a partial solution toward this problem by giving a complete answer to the following special case: Given a finite antichain P and 1-point-extensions Q_0, ..., Q_n placing a single point below some of the elements of P, which combinations of P and Q_0, ..., Q_n ensure that any embedding of P into the Sigma^0_2-enumeration degrees can be extended to such an embedding of Q_i for some i?
« Back... Spectra of structures and theories
Joseph Miller, University of Wisconsin, USA
The spectrum of a countable structure M is the set of all Turing degrees that compute a presentation of M. The spectrum of a complete theory T is the set of all degrees that present models of T. Although many of the spectra the are known to be possible for structures are also spectra of theories, we give an example of a structure spectrum that is not a theory spectrum. In the other direction, we show that the PA degrees (the degree of complete consistent extensions of Peano Arithmetic) are a theory spectrum but not a structure spectrum, providing a new example of a spectrum that is impossible for structures and showing that neither type of spectrum subsumes the other. Theory spectra are new to our work and very basic questions remain. (Joint work with Uri Andrews.)
« Back... Partial functions and domination
Frank Stephan, National University of Singapore
The current work introduces the notion of pdominant sets and studies their recursion-theoretic properties. Here a set A is called pdominant iff there is a partial A-recursive function psi such that for every partial-recursive function phi and almost every x in the domain of phi there is a y in the domain of psi with y leq x and psi(y) > phi(x). While there is a full Pi-0-1-class of nonrecursive sets where no set is pdominant, there is no Pi-0-1-class containing only pdominant sets. No weakly 2-generic set is pdominant while there are pdominant 1-generic sets below K. The halves of Chaitin's Omega are pdominant. There is a high r.e. set which is not pdominant. No set which is low for Martin-Loef random is pdominant.
Joint work: This is joint work with Chitat Chong, Gordon Hoi and Dan Turetsky.
« Back...
|
|