Computability Learning Seminar

Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo

"Comparing Structures"

In Computability Theory we have tools to compare the complexities of sets of natural numbers, tools like: Turing reducibility, enumeration reducibility, many-one reducibility, etc. For structures there are also various ways. For example have Muchnik reducibility, Medvedev reducibility, effective interpretability (also known as $\Sigma$-definability), and effective bi-interpretability. We are going to talk about Muchnik and Medvedev reducibilities.

MC 5403