Mariya Soskova : An enumeration degree perspective for effective mathematics

Posted by James Freitag , part of the Logic Seminar.

At

Sept. 18, 2018, 3:30 p.m.

In

427 SEO

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.