Computability Learning Seminar

Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo

"Muchnik and Medvedev Reducibilities"

Even though both reducibilities seemed to behave in a similar way, we could see (without proof), that they differ at how they get affected by adding a constant to the structures. We give a proof this time and also show in another result that the difference is more than just the reactions to adding constants. The latter result will require a version of the Slaman-Wehner structure.

MC 5403