[Zurück]

E. Fokina:
"Decidability, effective categorictiy and complexity of descriptions";
Vortrag: South Eastern Logic Symposium, Gainesville, Florida, USA (eingeladen); 27.02.2016 - 28.02.2016.

We call a structure categorical relative to n-decidable presentations (or autostable relative to n-constructivizations) if any two n-decidable copies of A are computably isomorphic.
For n = 0, we get the classical Definition of a computably categorical (autostable) structure.
Downey, Kach, Lempp, Lewis, Montalbán and Turetsky proved that there is no simple syntactic characterization of computable categoricity. More formally, they showed that the index set of computable categorical structures is pi1/1-complete.
In this talk we study the complexity of index sets of structures that are n-decidable and categorical relative to m-decidable presentations, for various m,n Epsilon w.
This is joint work with S. Goncharov, V. Harizanov, O. Kudinov and D. Turetsky.