Abstract: Complexity measures are designed to capture complex behavior and quantify *how* complex, according to that measure, that particular behavior is. It can be expected that different complexity measures from possibly entirely different fields are related to each other in a non-trivial fashion. Here we study small Turing machines (TMs) with two symbols, and two and three states. For any particular such machine and any particular input we consider what we call the 'space-time' diagram which is the collection of consecutive tape configurations of the computation . In our setting, we define fractal dimension of a Turing machine as the limiting fractal dimension of the corresponding space-time diagram. It turns out that there is a very strong relation between the fractal dimension of a Turing machine of the above-specified type and its runtime complexity. In particular, a TM with three states and two colors runs in at most linear time iff its dimension is 2, and its dimension is 1 iff it runs in super-polynomial time and it uses polynomial space. If a TM runs in time we have empirically verified that the corresponding dimension is , a result that we can only partially prove. We find the results presented here remarkable because they relate two completely different complexity measures: the geometrical fractal dimension on the one side versus the time complexity of a computation on the other side.
Recommendations
- Fractal dimension of random processes
- Dimensionality and fractals
- Fractal dimensions of the Rosenblatt process
- scientific article; zbMATH DE number 2154226
- scientific article; zbMATH DE number 2063224
- scientific article; zbMATH DE number 2216397
- Algorithmic Complexity and Thermodynamics of Fractal Growth Processes
- Fractal dimensions: Computational problems
- scientific article; zbMATH DE number 722162
- scientific article; zbMATH DE number 1304794
Cites work
- scientific article; zbMATH DE number 1670880 (Why is no real title available?)
- scientific article; zbMATH DE number 1818513 (Why is no real title available?)
- scientific article; zbMATH DE number 4093436 (Why is no real title available?)
- scientific article; zbMATH DE number 41255 (Why is no real title available?)
- scientific article; zbMATH DE number 47345 (Why is no real title available?)
- scientific article; zbMATH DE number 1994007 (Why is no real title available?)
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- scientific article; zbMATH DE number 2216397 (Why is no real title available?)
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- A formal theory of inductive inference. Part II
- A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
- Algorithmic randomness and complexity.
- An introduction to Kolmogorov complexity and its applications
- Complexity and randomness
- Compression-based investigation of the dynamical properties of cellular automata and other systems
- Computability of Julia sets
- Constructive dimension equals Kolmogorov complexity
- Correspondence principles for effective dimensions
- Dynamics in One Complex Variable. (AM-160)
- Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
- Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
- Frontier between decidability and undecidability: A survey
- Irreducibility and computational equivalence. 10 years after Wolfram's a new kind of science
- On Sets of Fractional Dimensions (III)
- On non-computable functions
- On the sum of digits of real numbers represented in the dyadic system. (On sets of fractional dimensions II.)
- Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
- Sets of Fractional Dimensions (IV): On Rational Approximation to Real Numbers
- Sets of Fractional Dimensions (V): on Dimensional Numbers of Some Continuous Curves
- Small fast universal Turing machines
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The dimensions of individual strings and sequences
- The measure theory of random fractals
- Two definitions of fractional dimension
- ∑1-Density and Turing Degrees
Cited in
(3)
This page was built for publication: Fractal dimension versus process complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q504699)
