Feasible analysis, randomness, and base invariance

DOI10.1007/s00224-013-9507-7zbMath1336.03047MaRDI 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

normality; martingales; analysis; base invariance; polynomial time randomness

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D32: Algorithmic randomness and dimension

03D78: Computation over the reals, computable analysis

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