University Seminar: Logic Across Disciplines-Computable Classification Problem

Title:   Computable Classification Problem

Speaker:    Valentina Harizanov, GWU

Date and Time: Thursday, November 2, 2017, 02:30pm-03:30pm

Place: Rome Hall 771

Abstract:  The Scott Isomorphism Theorem says that for any countable structure M there is a sentence, in countable infinitary language, the countable models of which are exactly the isomorphic copies of M. Here, we consider a computable structure A and define its index set to be the set of all Gödel codes for computable isomorphic copies of A. We will present evidence for the following thesis. To calculate the precise complexity of the index set of A, we need a good description of A, using computable infinitary language, and once we have an optimal description, the exact complexity within a computability-theoretic hierarchy will match that of the description.