A polynomial-time algorithm for computing absolutely normal numbers

DOI10.1016/j.ic.2013.08.013zbMath1315.03075OpenAlexW2148274234WikidataQ61927017 ScholiaQ61927017MaRDI QIDQ386000

Theodore A. Slaman, Verónica Becher, Pablo Ariel Heiber

Publication date: 13 December 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2013.08.013

zbMATH Keywords

algorithmabsolutely normal numbercomputable

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Applications of computability and recursion theory (03D80)

Related Items (16)

Dynamical Systems and Uniform Distribution of Sequences ⋮ On a question of Mendès France on normal numbers ⋮ Normality of different orders for Cantor series expansions ⋮ Finite-state independence and normal sequences ⋮ Normal Numbers and Computer Science ⋮ Derandomization in game-theoretic probability ⋮ A note on the points with dense orbit under the expansions of different bases ⋮ Liouville, computable, Borel normal and Martin-Löf random numbers ⋮ Computing absolutely normal numbers in nearly linear time ⋮ A computable absolutely normal Liouville number ⋮ Unexpected distribution phenomenon resulting from Cantor series expansions ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ Normality in non-integer bases and polynomial time randomness ⋮ Computable absolutely normal numbers and discrepancies ⋮ M. Levin’s construction of absolutely normal numbers with very low discrepancy ⋮ Feasible analysis, randomness, and base invariance

Cites Work

• Turing's unpublished algorithm for normal numbers
• Über die Normalität von Zahlen zu verschiedenen Basen
• An example of a computable absolutely normal number
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial-time algorithm for computing absolutely normal numbers