A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
M. Levin’s construction of absolutely normal numbers with very low discrepancy
Among the currently known constructions of absolutely normal numbers, the one given by Mordechay Levin in 1979 achieves the lowest discrepancy bound. In this work we analyze this construction in terms of computability and computational complexity. We show that, under basic assumptions, it yields a computable real number. The construction does not give the digits of the fractional expansion explicitly, but it gives a sequence of increasing approximations whose limit is the announced absolutely normal number. The nth approximation has an error less than 2–2n. To obtain the $ nth approximation the construction requires, in the worst case, a number of mathematical operations that is doubly exponential in n. We consider variants on the construction that reduce the computational complexity at the expense of an increment in discrepancy. ; Fil: Alvarez, Nicolás Alejandro. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Ciencias e Ingeniería de la Computación. Universidad Nacional del Sur. Departamento de Ciencias e Ingeniería de la Computación. Instituto de Ciencias e Ingeniería de la Computación; Argentina ; Fil: Becher, Veronica Andrea. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
M. Levin’s construction of absolutely normal numbers with very low discrepancy
Among the currently known constructions of absolutely normal numbers, the one given by Mordechay Levin in 1979 achieves the lowest discrepancy bound. In this work we analyze this construction in terms of computability and computational complexity. We show that, under basic assumptions, it yields a computable real number. The construction does not give the digits of the fractional expansion explicitly, but it gives a sequence of increasing approximations whose limit is the announced absolutely normal number. The nth approximation has an error less than 2–2n. To obtain the $ nth approximation the construction requires, in the worst case, a number of mathematical operations that is doubly exponential in n. We consider variants on the construction that reduce the computational complexity at the expense of an increment in discrepancy. ; Fil: Alvarez, Nicolás Alejandro. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Ciencias e Ingeniería de la Computación. Universidad Nacional del Sur. Departamento de Ciencias e Ingeniería de la Computación. Instituto de Ciencias e Ingeniería de la Computación; Argentina ; Fil: Becher, Veronica Andrea. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
M. Levin’s construction of absolutely normal numbers with very low discrepancy
Alvarez, Nicolás Alejandro (author) / Becher, Veronica Andrea (author)
CONICET
Article (Journal)
Electronic Resource
English
| British Library Online Contents | 2014
TIME OUT IN KEY WEST Barbara Riley Levin and Gerald M. Levin's Florida Haven
| British Library Online Contents | 2003
| British Library Online Contents | 2018
Online Contents | 1995
INarts : ABSOLUTELY: MCCRACKEN
| Online Contents | 2010