[Back]

D. Rossegger:
"Enumerable Functors";
Talk: Logic Colloquium 2016, Leeds, UK (invited); 2016-07-31 - 2016-08-06.

We propose a new notion of reducibility between structures, enumerable functors, inspired by the recently investigated notion of computable functors [1], [2]. An enumerable functor from a structure A to a structure B is a pair (Ψ,Φ) where Ψ is an enumeration operator transforming every presentation of A to a presentation of B and Φ is a Turing functional transforming every isomorphism between two presentations of A to an isomorphism of their image. Our main results are that enumerable functors preserve Σn-spectra [3] and that they are equivalent to a restricted version of effective interpretability. We also extend this equivalence to effective bi-interpretability and reducibility between classes of structures by effective bi-interpretability.