test FOO test
Computability in Europe 2006
Logical Approaches to Computational Barriers
In 1944, Post  set out to relate computational structure to its
information content. Since then, many computability-theoretic classes
captured, in the spirit of Post, via their relationships to the
lattice of computably
enumerable (c.e.) sets. In particular, we have Post's 
characterisation of the
non-computable c.e. Turing degrees as those of the simple, or
sets; Martin's Theorem  showing the high c.e. Turing degrees to be
containing maximal sets; and Shoenfield's  characterisation of
c.e. degrees as those of the atomless c.e. sets (that is, of
co-infnite c.e. sets
without maximal supersets).
In this talk, and in Afshari, Barmpalias and Cooper , I initiate
extension of Post's programme to computability-theoretic classes of
For basic terminology and notation, see Cooper , Soare , or
1. B. Afshari, G. Barmpalias and S. B. Cooper, Characterising the
highness of d.c.e. degrees, in preparation.
2. G. Barmpalias, Hypersimplicity and Semicomputability in the Weak
Truth Table Degrees, Archive for Math. Logic Vol.44, Number 8 (2005) 1045-1065.
3. G. Barmpalias and A. Lewis, The Hypersimple-free c.e. wtt degrees
are dense in the c.e. wtt degrees, to appear in Notre Dame Journal of Formal
4. S. B. Cooper, Computability Theory, Chapman & Hall/ CRC Press,
Boca Raton, FL, New York, London, 2004.
5. A. H. Lachlan, On the lattice of recursively enumerable sets,
Trans. Am. Math. Soc. 130 (1968), 1-37.
6. D. A. Martin, Classes of recursively enumerable sets and degrees
of unsolvability, Z. Math. Logik Grundlag. Math. 12 (1966), 295-310.
7. P. Odifreddi, Classical recursion theory Vols. I,II Amsterdam
Oxford: North-Holland, 1989, 1999.
8. J. C. Owings, Recursion, metarecursion and inclusion, Journal of
Symbolic Logic 32 (1967), 173-178.
9. E. L. Post, Recursively enumerable sets of positive integers and
their decision problems, Bull. Am. Math. Soc. 50 (1944), 284-316.
10. J. R. Shoen_eld, Degrees of classes of r.e. sets, J. Symbolic
Logic 41 (1976), 695-696.
11. R. I. Soare, Recursively enumerable sets and degrees,
Springer-Verlag, Berlin, London, 1987.
websites: Arnold Beckmann