[Zurück]

D. Rossegger, E. Fokina:
"Enumerable functors";
Vortrag: ASL European Summer Meeting - Logic Colloquium 2016, Leeds, UK (eingeladen); 31.07.2016 - 06.08.2016.

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.

enumerable functors, computable functors, effective interpretability