Verónica Becher

An example of a computable absolutely normal number

2002, Theoretical Computer Science 270 (1-2), 947-958, 2002
Citas: 98
Importar citas Plots Conexiones

Autor(es)

Verónica Becher and Santiago Figueira

URL Pública

https://www.sciencedirect.com/science/article/pii/S0304397501001700

Abstract

The first example of an absolutely normal number was given by Sierpinski in 1916, twenty years before the concept of computability was formalized. In this note we give a recursive reformulation of Sierpinski's construction which produces a computable absolutely normal number.

Plot de citas

Citas de Scrapping

# Año #Citas Título Autores Journal Editor
1 2011 861 Ergodic theory M Einsiedler 2011 Springer
2 2013 858 Information and randomness: an algorithmic perspective CS Calude 2013 books.google.com
3 2008 743 Mathematics by experiment J Borwein, D Bailey 2008 api.taylorfrancis.com
4 2014 67 Algorithmic complexity for short binary strings applied to psychology: a primer N Gauvrit, H Zenil, JP Delahaye…  Behavior research …, 2014 Springer
5 2022 11 Stationary processes and discrete parameter Markov processes R Bhattacharya, EC Waymire 2022 books.google.com
6 2022 12 Emergence and algorithmic information dynamics of systems and observers FS Abrahão, H Zenil  Philosophical Transactions of the …, 2022 royalsocietypublishing.org
7 2006 57 Large alphabets and incompressibility T Gagie  Information Processing Letters, 2006 Elsevier
8 2013 46 A polynomial-time algorithm for computing absolutely normal numbers V Becher, PA Heiber, TA Slaman  Information and Computation, 2013 Elsevier
9 2007 59 Turing's unpublished algorithm for normal numbers V Becher, S Figueira, R Picchi  Theoretical Computer Science, 2007 Elsevier
10 2009 43 A constructive Borel–Cantelli lemma. Constructing orbits with required statistical properties S Galatolo, M Hoyrup, C Rojas  Theoretical Computer Science, 2009 Elsevier
11 2011 31 Mathematical foundations of randomness A Dasgupta  Philosophy of Statistics, 2011 Elsevier
12 2018 16 Normal numbers and computer science V Becher, O Carton  Sequences, groups, and number theory, 2018 Springer
13 2301 1 Lacunary sequences in analysis, probability and number theory C Aistleitner, I Berkes, R Tichy  arXiv preprint arXiv:2301.05561, 2023 arxiv.org
14 2021 6 Computable measure theory and algorithmic randomness M Hoyrup, J Rute  Handbook of Computability and Complexity in Analysis, 2021 Springer
15 1610 15 Computable absolutely Pisot normal numbers MG Madritsch, AM Scheerer, RF Tichy  arXiv preprint arXiv:1610.06388, 2016 arxiv.org
16 2014 22 Number theoretic applications of a class of Cantor series fractal functions. I B Mance  Acta Mathematica Hungarica, 2014 Springer
17 2018 12 Sequences, groups, and number theory V Berthé, M Rigo 2018 Springer
18 2021 6 Algorithmic information distortions in node-aligned and node-unaligned multidimensional networks FS Abrahão, K Wehmuth, H Zenil, A Ziviani  Entropy, 2021 mdpi.com
19 2017 15 Computable absolutely normal numbers and discrepancies AM Scheerer  Mathematics of Computation, 2017 ams.org
20 2009 27 Indifferent sets S Figueira, JS Miller, A Nies  Journal of Logic and Computation, 2009 ieeexplore.ieee.org
21 2006 23 Normal numbers are normal D Khoshnevisan  Clay Mathematics Institute Annual Report, 2006 claymath.org
22 2023 3 Poisson generic sequences N Álvarez, V Becher, M Mereb  … Mathematics Research Notices, 2023 academic.oup.com
23 2016 14 Finite state incompressible infinite sequences CS Calude, L Staiger, F Stephan  Information and Computation, 2016 Elsevier
24 2020 6 Patterns and Probabilities: A Study in Algorithmic Randomness and Computable Learning FZ Blando 2020 search.proquest.com
25 2015 20 Feasible analysis, randomness, and base invariance S Figueira, A Nies  Theory of Computing Systems, 2015 Springer
26 2010 17 Some bridging results and challenges in classical, quantum and computational randomness G Longo, C Palamidessi, T Paul  World Sci, 2010 books.google.com
27 0908 18 Words and transcendence M Waldschmidt  arXiv preprint arXiv:0908.4034, 2009 arxiv.org
28 1701 8 On the continued fraction expansion of absolutely normal numbers AM Scheerer  arXiv preprint arXiv:1701.07979, 2017 arxiv.org
29 2016 9 On dynamical systems for transport logistic and communications AP Buslaev, AG Tatashev  Journal of Mathematics …, 2016 pdfs.semanticscholar.org
30 2012 12 On the expansions of a real number to several integer bases Y Bugeaud  Revista Matemática Iberoamericana, 2012 ems.press
31 2008 17 Measures of complexity for artificial embryogeny T Kowaliw  Proceedings of the 10th annual conference on Genetic …, 2008 dl.acm.org
32 2013 14 Champernowne's number, strong normality, and the X chromosome A Belshaw, P Borwein  … and Analytical Mathematics: In Honor of Jonathan …, 2013 Springer
33 2012 14 Nonnormality of Stoneham constants DH Bailey, JM Borwein  The Ramanujan Journal, 2012 Springer
34 2017 9 M. Levin's construction of absolutely normal numbers with very low discrepancy N Alvarez, V Becher  Mathematics of Computation, 2017 ams.org
35 2012 11 Turing's normal numbers: towards randomness V Becher  Conference on Computability in Europe, 2012 Springer
36 2012 6 Hartmanis-Stearns conjecture on real time and transcendence R Freivalds  … Conference on Teaching and Computational Science, 2012 Springer
37 2015 8 Number theoretic applications of a class of Cantor series fractal functions, II B Li, B Mance  International Journal of Number Theory, 2015 World Scientific
38 2020 3 Quantifying nonrandomness in evolving networks PK Pandey, M Singh  IEEE Transactions on Computational …, 2020 ieeexplore.ieee.org
39 2023 0 Normality, Relativization, and Randomness W Calvert, E Grunner, E Mayordomo, D Turetsky…  arXiv preprint arXiv …, 2023 arxiv.org
40 2010 6 Structural metrics: an epistemology MB Winter 2010 search.proquest.com
41 2013 4 Liouville numbers, Borel normality and algorithmic randomness CS Calude, L Staiger 2013 researchspace.auckland.ac.nz
42 2013 4 An experimental investigation of the normality of irrational algebraic numbers J Nielsen, J Simonsen  Mathematics of Computation, 2013 ams.org
43 2022 0 Algorithmic Complexity in Cognition H Zenil, FS Toscano, N Gauvrit  Methods and Applications of Algorithmic …, 2022 Springer
44 2017 4 Turing and randomness. R Downey 2017 homepages.ecs.vuw.ac.nz
45 2020 2 Methods and applications of algorithmic complexity H Zenil, N Kiani, J Tegnér 2020 Springer
46 2022 0 Methods and Applications of Algorithmic Complexity: Beyond Statistical Lossless Compression H Zenil, FS Toscano, N Gauvrit 2022 books.google.com
47 2010 3 Ergodic theory M Einsiedler, T Ward 2010 Citeseer
48 2007 5 A good number of forms fairly beautyful T Kowaliw 2007 Citeseer
49 2202 0 Poisson generic sequences NAVBM Mereb  arXiv preprint arXiv:2202.01632, 2022 researchgate.net
50 2006 5 Diophantine analysis and words M Waldschmidt  Diophantine analysis and related fields 2006, 2006 webusers.imj-prg.fr
51 2023 1 Transcendence of numbers related to Episturmian words P Kebis 2023 ora.ox.ac.uk
52 2018 2 Fractal analysis of Pi normality C Sevcik  Experimental Mathematics, 2018 Taylor & Francis
53 1702 2 On absolutely normal numbers and their discrepancy estimate V Becher, AM Scheerer, T Slaman  arXiv preprint arXiv:1702.04072, 2017 arxiv.org
54 2013 2 Strong Normality, Modular Normality, and Flat Polynomials: Applications of Probability in Number Theory and Analysis AW Belshaw 2013 summit.sfu.ca
55 1106 3 Assessing cognitive randomness: A kolmogorov complexity approach N Gauvrit, H Zenil, JP Delahaye  arXiv preprint arXiv:1106.3059, 2011 researchgate.net
56 2007 4 An effective Borel-Cantelli lemma. Constructing orbits with required statistical properties S Galatolo, M Hoyrup, C Rojas  arXiv, 2007 Citeseer
57 0708 3 Empirical entropy in context T Gagie  arXiv preprint arXiv:0708.2084, 2007 arxiv.org
58 2014 2 Computability theory, algorithmic randomness and Turing's anticipation. R Downey 2014 books.google.com
59 2018 1 On incompressible multidimensional networks FS Abrahão, K Wehmuth, H Zenil, A Ziviani  arXiv preprint arXiv …, 2018 arxiv.org
60 2004 3 The Theory of Everything and the future of life T Karthik  International Journal of Astrobiology, 2004 cambridge.org
61 2006 6 Propriétés combinatoires et arithmétiques de certaines suites automatiques et substitutives J Albert 2006 theses.hal.science
62 2022 0 An Introduction to Dynamical Systems R Bhattacharya, E Waymire  Stationary Processes and Discrete …, 2022 Springer
63 2008 7 Caractérisations de l'aléatoire par les jeux: impredictibilité et stochasticité L Bienvenu 2008 Citeseer
64 2004 0 The “cardinality of extended solution set” criterion for establishing the intractability of NP problems U Arun  arXiv preprint arXiv:2004.01491, 2020 arxiv.org
65 2010 1 RANDOMNESS: FOUR QUESTIONS AND SOME CHALLENGES G Longo, C Palamidessi, T PAUL  Zenil H.(ed. by), Randomnes, 2010 hal.science
66 2008 1 Game-theoretic approaches to randomness: unpredictability and stochasticity. L Bienvenu 2008 theses.hal.science
67 2007 1 A good number of forms fairly beautiful: an exploration of biologically-inspired automated design T Kowaliw 2007 spectrum.library.concordia.ca
68 2006 1 Normale Zahlen C Aistleitner 2006 math.tugraz.at
69 0902 1 New algorithms and lower bounds for sequential-access data compression T Gagie  arXiv preprint arXiv:0902.0133, 2009 arxiv.org
70 2006 4 Два подхода к оценке математики как феномена культуры: Франция и Россия, 1890-1930 гг. Л Грэхэм, ЖМ Кантор  Вопросы истории естествознания и техники, 2006 elibrary.ru
71 2006 1 Aspects of randomness S Figueira 2006 Citeseer
72 2018 0 Algorithmic information distortions and incompressibility in uniform multidimensional networks FS Abrahão, K Wehmuth, H Zenil, A Ziviani  arXiv preprint arXiv …, 2018 arxiv.org
73 2018 0 Algorithmically random generalized graphs and its topological properties FS Abrahão, K Wehmuth, H Zenil, A Ziviani  arXiv, 2018 dml.mathdoc.fr
74 2015 0 ON THE COMPLEXITY OF THE β-EXPANSIONS OF ALGEBRAIC NUMBERS JH EVERTSE 2015 math.u-bordeaux.fr
75 2015 0 An encryption algorithm A Soloi  2015 7th International Conference on Electronics …, 2015 ieeexplore.ieee.org
76 0 Randomnes: five questions and some challenges G Longo, C Palamidessi, P Thierry hal.science
77 2013 0 An Introduction to Ergodic Theory Normal Numbers: We Can't See Them, But They're Everywhere! J Horan 2013 math.uvic.ca
78 2011 0 A Reinterpretation, and New Demonstrations of, the Borel Normal Number Theorem DL Rockwell 2011 search.proquest.com
79 1105 0 What Maxwell's demon could do for you K Svozil  arXiv preprint arXiv:1105.4768, 2011 arxiv.org
80 2013 1 Das Zufallsprinzip. Vom Ereignis zum Gesetz H Kuthan 2013 books.google.com
81 2021 0 Algebralliset luvut M Aaltonen 2021 trepo.tuni.fi
82 2008 0 Randomness and Ergodic Theory: An Algorithmic Point of View CR González 2008 researchspace.auckland.ac.nz
83 2007 0 On the normality of normal numbers D KHOSHNEVISAN 2007 Citeseer
84 2010 1 Nociones de aleatoriedad y transformaciones de cambio de base A Taraciuk 2010 gestion.dc.uba.ar
85 2006 1 On normal numbers D Pellegrino  Proyecciones (Antofagasta), 2006 SciELO Chile
86 2018 0 Méthodes analytiques, probabilistes et dynamiques dans l'étude des systèmes de numération M Madritsch 2018 hal.science
87 2014 0 Cómputo eficiente de números absolutamente normales M Epszteyn 2014 www-2.dc.uba.ar
88 2014 0 Una perspectiva computacional sobre números normales PA Heiber 2014 bibliotecadigital.exactas.uba.ar
89 0 Tesis de Licenciatura LI Cavatorta gestion.dc.uba.ar
90 2006 0 Aspectos de aleatoriedad SD Figueira 2006 bibliotecadigital.exactas.uba.ar
91 2018 4 FS Abrahao, K Wehmuth, H Zenil, A Ziviani 2018 Research report
92 2007 1 SH Khayat  … Department Ferdowsi University of Mashhad, Iran, 2007
93 0 FS ABRAHAO, K WEHMUTH, H ZENIL, A ZIVIANI
94 0 V Becher, O Carton
95 0 C ROJAS
96 2008 0 G LONGO 2008
97 2003 0 JM Borwein, DH Bailey 2003
98 2008 0 ME ASARIN 2008 Royal Holloway

Referencias

# Title Year Source Authors
1 Les probabilite's de'nombrables et leurs applications arithme'tiques, Rend 1909 Circ. Mat. Palermo E. Borel
2 A theory of program size formally identical to information theory 1975 ACM G.J. Chaitin
3 'le'mentaire du the' 1917 Bull. Soc. Math. France M.W. Sierpinski
4 A note on normal numbers 1992 Collected Works of A. M. Turing, Pure Mathematics A. Turing

Figuras

...
...