We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
COMPUTABLE FUNCTORS AND EFFECTIVE INTERPRETABILITY.
- Authors
Harrison-Trainor, Matthew; Melnikov, Alexander; Miller, Russell; Montalbán, Antonio
- 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.
- Subjects
COMPUTABLE model theory; COMPUTATIONAL statistics; DEFINABILITY theory (Mathematical logic); COMPUTABILITY logic; COMPUTABLE functions
- Publication
Journal of Symbolic Logic, 2017, Vol 82, Issue 1, p77
- ISSN
0022-4812
- Publication type
Article
- DOI
10.1017/jsl.2016.12