Algebraic structures: Computability vs Automaticity

2019/01/16 Wed 16:30 - 17:30
Room 110, RIMS
Bakhadyr Khoussainov
University of Auckland

How does one introduce computability into the study of algebraic structures,
such as groups, vector spaces, algebras? In answering this question we
provide two classical definitions. One is the notion of computable structure first
introduced by Malcev and Rabin in the early 60s. The other is the notion of
automatic structure first observed by Thurston (in the 80s) in the classes of groups, and then further developed in the general setting by Nerode and the speaker. The
presentation will be introductory with examples, motivation, and general background to the topics of both the theory of computable structures and the theory of automatic
The talk will be aimed at the general mathematics/computer science audience.