Recursive Reducibility Relations on Pi01 subsets of the Cantor Set, part 1

Series: Penn State Logic Seminar

Date: Tuesday, October 1, 2002

Time: 2:30 - 3:45 PM

Place: 312 Boucke Building

Speaker: Stephen E. Binns, Mathematics, Penn State

Title: 

Recursive Reducibility Relations on Pi01 subsets of the Cantor Set,
part 1.

Abstract: 

This talk is an introduction to Medvedev and Muchnik reducibility, and
some basic results on embeddings into the resultant degree structures
on the class of Pi^0_1 sets.  We show how these results can be used to
prove the decidability of the relevant E-theories.