Feasible analysis, randomness, and base invariance

DOI10.1007/s00224-013-9507-7zbMath1336.03047OpenAlexW2074176469MaRDI QIDQ2354578

André Nies, Santiago Figueira

Publication date: 20 July 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9507-7

zbMATH Keywords

normalitymartingalesanalysisbase invariancepolynomial time randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78)

Related Items

Normal Numbers and Computer Science, Computing absolutely normal numbers in nearly linear time, Normality in non-integer bases and polynomial time randomness, Closure of resource-bounded randomness notions under polynomial time permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial-time algorithm for computing absolutely normal numbers
• On normal numbers
• Turing's unpublished algorithm for normal numbers
• A decomposition theorem for numbers in which the summands have prescribed normality properties
• Diagonalizations over polynomial time computable sets
• Almost everywhere high nonuniform complexity
• Resource bounded randomness and weakly complete problems
• The primes contain arbitrarily long arithmetic progressions
• Base invariance of feasible dimension
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Randomness and differentiability
• Category and Measure in Complexity Classes
• The Construction of Decimals Normal in the Scale of Ten
• A unified approach to the definition of random sequences
• The definition of random sequences
• An example of a computable absolutely normal number
• Randomness as an invariant for number representations