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.