Algebraic structures: Computability vs Automaticity

開催日時: 
2019/01/16 Wed 16:30 - 17:30
場所: 
RIMS110号室
講演者: 
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
structures.
The talk will be aimed at the general mathematics/computer science audience.