A STUDY OF RANDOMNESS AND GROUPS USING FINITE AUTOMATA

Abstract

The thesis aims to study randomness and mathematical groups from automata-theoretic perspective. A general approach to study random objects is taken from Algorithmic Randomness, while that for groups is taken from Computable Model Theory.

A study of randomness in this thesis proceeds in several directions. Firstly, automatic randomness tests are introduced as a measure-theoretic tool to detect randomness. Secondly, globally automatic supermartingales are introduced as predicting machines on infinite sequences. Thirdly, a notion of randomness is extended from infinite sequences to formal languages using automatic martingales which are locally automatic. Finally, we answer the open question on subword complexity, which asks if any real in the unit interval acts as a value for subword complexity.

As for study of groups, it proceeds in two directions. Firstly, presentations of various Lamplighter groups using transducers are studied. Secondly, we investigate various mathematical structures with two-way finite automata recognisable presentations.