University Seminars: Logic Across Disciplines-Computability and definability

Title:  Computability and definability
Speaker:   Valentina Harizanov, GWU
https://home.gwu.edu/~harizanv/
Date and Time:  Friday, October 19 2018, 01:00pm-02:00pm
Place: Rome Hall (801 22nd Street), Room 771

Abstract: Since classical isomorphisms do not preserve computable properties of structures, computability theorists are interested in computable isomorphisms. We say that a computable structure is computably categorical if for every isomorphic computable structure there is a computable isomorphism. We will give examples and counterexamples of computable categoricity, and show how definable properties of structures relate to categoricity. For many structures from natural classes, there is a characterization of computably categorical ones. The notion of computable categoricity can be generalized by looking at isomorphisms that are computable from Turing’s halting set, leading to many open characterization problems.