October 5
Iskander Kalimullin,
Kazan Federal University
Primitive recursive structures and isomorphisms
It is known that every computable relational structure is isomorphic to a primitive recursive structure on a primitive recursive universe. This talk is devoted to the primitive recursive structures with the universe consisting of all natural numbers. This is a new notion which indeed is stronger than the standard notion. However, the new notion allows us to obtain non-trivial results on the complexity of isomorphisms between primitive recursive copies of structures. In this talk I will give a survey of the results obtained by myself, A. Melnikov, K.M. Ng and others.