Rice sequences of relations.
We propose a framework to study the computational complexity of definable relations on a structure. Many of the notions we discuss are old, but the viewpoint is new. We believe that all the pieces fit together smoothly under this new point of view. We also survey related results in the area. More concretely, we study the space of sequences of relations over a given structure. On this space, we develop notions of c.e.-ness, reducibility, join and jump. These notions are equivalent to other notions studied in other settings. We explain the equivalences and differences between these notions.
Department of Mathematics, University of Chicago, IL 60637, USA. antonio@math.uchicago.edu
Antonio
A
Montalbán