Kurt Gödel Research Center

2008 seminar talk: Reductions by computable functionals

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

Abstract

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.