Feasible analysis, randomness, and base invariance
From MaRDI portal
Publication:2354578
DOI10.1007/s00224-013-9507-7zbMath1336.03047MaRDI QIDQ2354578
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
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