Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Information Content and Computability in the n-C.E. Hierarchy

Speaker: Bahareh Afshari
Author(s): Bahareh Afshari, George Barmpalias and S. Barry Cooper
Slot: Array, 11:10-11:30, col. 1


In 1944, Post [9] set out to relate computational structure to its
information content. Since then, many computability-theoretic classes
have been
captured, in the spirit of Post, via their relationships to the
lattice of computably
enumerable (c.e.) sets. In particular, we have Post's [9]
characterisation of the
non-computable c.e. Turing degrees as those of the simple, or
hypersimple even,
sets; Martin's Theorem [6] showing the high c.e. Turing degrees to be
containing maximal sets; and Shoenfield's [10] characterisation of
the non-low2
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 [1], I initiate
extension of Post's programme to computability-theoretic classes of
the n-c.e.
For basic terminology and notation, see Cooper [4], Soare [11], or
Odifreddi [7].


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 2006-06-12