Logical Approaches to Computational Barriers

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 underlying 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 those 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 the extension of Post's programme to computability-theoretic classes of the n-c.e. sets. For basic terminology and notation, see Cooper [4], Soare [11], or Odifreddi [7]. References 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 Logic. 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 |