2008 seminar talk: Reductions by computable functionals

Talk held by Sebastiaan Terwijn (KGRC) at the KGRC seminar on 2008-04-03.


Turing reducibility is a central notion from computability theory measuring the relative computability of reals: A real A reduces to a real B if there is a computable functional mapping B to A. We can also use computable functionals to reduce sets of reals to each other. This gives rise to two structures generalizing the Turing degrees: The Medvedev and the Muchnik lattices. In this talk we will discuss some structural properties of these lattices.

Bottom menu

Kurt Gödel Research Center for Mathematical Logic. Währinger Straße 25, 1090 Wien, Austria. Phone +43-1-4277-50501. Last updated: 2010-12-16, 04:37.