Logic Seminar
Mariya Soskova
University of Wisconsin
An enumeration degree perspective for effective mathematics
Abstract: The Turing degrees measure the computability-theoretic complexity of elements of $2^\omega$. We can code other mathematical objects as binary sequences and use the Turing degrees to measure their complexity. However, this does not always lead to a coherent measure of complexity; there may not be a ``canonical'' coding. The enumeration degrees, a natural extension of the Turing degrees, work in some circumstances where Turing degrees fail. For example the enumeration degrees can measure the complexity of continuous functions on the unit interval. In fact, we get a proper subclass of the enumeration degrees: the continuous degrees. A larger subclass, the cototal degrees, arises naturally in symbolic dynamics, graph theory and computable structure theory.
Tuesday September 18, 2018 at 3:30 PM in 427 SEO