The arithmetical complexity of dimension and randomness

DOI10.1145/1227839.1227845MaRDI QIDQ5277778zbMATH OpenOpenAlexFDO

Authors John M. Hitchcock, Jack H. Lutz, Sebastiaan A. Terwijn

Publication date 12 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1227839.1227845

zbMATH Keywords

arithmetical hierarchycomputable randomnessconstructive dimensionSchnorr randomnessWadge reductions

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Applications of computability and recursion theory (03D80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Computer Science Logic
• scientific article; zbMATH DE number 1670880
• New Computational Paradigms
• The dimensions of individual strings and sequences
• Schnorr dimension

Cited in

(12)

• On the bounds for the complexity of generation of rational numbers by stochastic contact \(\pi{}\)-networks
• Arithmetic complexity via effective names for random sequences
• Schnorr dimension
• Connectivity properties of dimension level sets
• Connectivity properties of dimension level sets
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• Effective aspects of Hausdorff and Fourier dimension
• Lowness for effective Hausdorff dimension
• Computer Science Logic
• Constructive Dimension and Weak Truth-Table Degrees
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Constructive dimension and Turing degrees

This page was built for publication: The arithmetical complexity of dimension and randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277778)