INVESTIGADORES
BECHER veronica Andrea
capítulos de libros
Título:
Normal numbers and Computer Science
Autor/es:
VERÓNICA BECHER; OLIVIER CARTON
Libro:
Sequences, Groups, and Number Theory
Editorial:
Springer
Referencias:
Año: 2018;
Resumen:
Émile Borel defined normality more than one hundred years ago to formalize the most basic form of randomness for real numbers.A number is normal to a given integer base if its expansion in that base is such that all blocks of digits of the same length occur in it with the same limiting frequency.This chapter is an introduction to the theory of normal numbers.We present five different equivalent formulations of normality and we prove their equivalence in full detail. Four of the definitions are combinatorial and one is in terms of finite automata, analogous to the characterization of Martin-Löf randomness in terms of Turing machines.All known examples of normal numbers have been obtained by constructions. We show three constructions of numbers that are normal to a give baseand two constructions of numbers that are normal to all integer bases. We also prove Agafonov´s Theorem that establishes that a number is normal to a given base exactly when its expansion in that base is such that every subsequence selected by a finite automata is also normal.