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.
Reductions by computable functionals
03.04.2008 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25