Normal numbers and computer science

Émile Borel defined normality more than 100 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 chap...

Descripción completa

Detalles Bibliográficos
Publicado: 2018
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_22970215_v_n9783319691510_p233_Becher
http://hdl.handle.net/20.500.12110/paper_22970215_v_n9783319691510_p233_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_22970215_v_n9783319691510_p233_Becher
record_format dspace
spelling paper:paper_22970215_v_n9783319691510_p233_Becher2023-06-08T16:35:28Z Normal numbers and computer science Émile Borel defined normality more than 100 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 given base and 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 automaton is also normal. © Springer International Publishing AG, part of Springer Nature 2018. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_22970215_v_n9783319691510_p233_Becher http://hdl.handle.net/20.500.12110/paper_22970215_v_n9783319691510_p233_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
description Émile Borel defined normality more than 100 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 given base and 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 automaton is also normal. © Springer International Publishing AG, part of Springer Nature 2018.
title Normal numbers and computer science
spellingShingle Normal numbers and computer science
title_short Normal numbers and computer science
title_full Normal numbers and computer science
title_fullStr Normal numbers and computer science
title_full_unstemmed Normal numbers and computer science
title_sort normal numbers and computer science
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_22970215_v_n9783319691510_p233_Becher
http://hdl.handle.net/20.500.12110/paper_22970215_v_n9783319691510_p233_Becher
_version_ 1768544888615337984

Ejemplares similares