The existence of computable sequence that cannot be described by finite automata

The goal of the project is to construct an infinite sequence that cannot be generated by any simple automatic device, and to estimate its complexity. The conjecture on the existence of such a sequence is based on the idea of superiority of Turing machines over finite automata. In the project, a new notion of automaton martingale is introduced, and the existence of an infinite binary random sequence that cannot be generated by a finite automaton is proved. In order to reach the goal of the project one had to study Turing machines, finite automata, computable martingales, and the diagonalization method.