Logic seminar-Computable isomorphism problem

Time: Thursday, February 17, 11:00 am-12:00 noon

Place: zoom
https://gwu-edu.zoom.us/j/94863523471

Speaker:  Valentina Harizanov, GWU

Title: Computable isomorphism problem

Abstract: For certain well-known classes of algebraic structures we investigate computability-theoretic complexity of the isomorphism problem for its computable members. While for some structures, the computable isomorphism problem is complete at various levels of arithmetical hierarchy, we will focus on structures with Sigma-1-1 complete isomorphism problem, which is of maximal complexity. One of the methods we use to establish such results is based on effective interpretations of computable structures from one class into computable structures from another class.