4 papers
The Arithmetical Complexity of Dimension and Randomness
John M. Hitchcock, Jack H. Lutz, Sebastiaan A. Terwijn
Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a d…
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz +1
The two most important notions of fractal dimension are {\it Hausdorff dimension}, developed by Hausdorff (1919), and {\it packing dimension}, developed by Tricot (1982). Lutz (200…
The Dimensions of Individual Strings and Sequences
Jack H. Lutz
A constructive version of Hausdorff dimension is developed using constructive supergales, which are betting strategies that generalize the constructive supermartingales used in the…
Dimension in Complexity Classes
Jack H. Lutz
A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound Δ(a parameter of the theory) is unrestric…