COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY
Matthew Harrison‐Trainor, Alexander Melnikov, Russell Miller, Antonio Montalbán · Journal of Symbolic Logic · 2017
Abstract Our main result is the equivalence of two notions of reducibility between structures. One is a syntactical notion which is an effective version of interpretability as in model theory, and the other one is a computational notion which is a strengthening of the well-known Medvedev reducibility. We extend our result to effective bi-interpretability and also to effective reductions between classes of structures.