Fractal dimension versus process complexity

DOI10.1155/2016/5030593zbMATH Open1401.68078arXiv1309.1779OpenAlexW2963260578WikidataQ59122514 ScholiaQ59122514MaRDI QIDQ504699FDOQ504699

Authors: Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil 

Publication date: 17 January 2017

Published in: Advances in Mathematical Physics (Search for Journal in Brave)

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 $au$ and any particular input $x$ we consider what we call the 'space-time' diagram which is the collection of consecutive tape configurations of the computation $au(x)$. 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 $O(x^n)$ we have empirically verified that the corresponding dimension is $(n+1)/n$, 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.

Full work available at URL: https://arxiv.org/abs/1309.1779

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Fractals (28A80)

Cites Work

• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Title not available (Why is that?)
• Algorithmic randomness and complexity.
• Two definitions of fractional dimension
• Title not available (Why is that?)
• Sets of Fractional Dimensions (IV): On Rational Approximation to Real Numbers
• Compression-based investigation of the dynamical properties of cellular automata and other systems
• Dynamics in One Complex Variable. (AM-160)
• The dimensions of individual strings and sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part II
• Sets of Fractional Dimensions (V): on Dimensional Numbers of Some Continuous Curves
• Constructive dimension equals Kolmogorov complexity
• On the sum of digits of real numbers represented in the dyadic system. (On sets of fractional dimensions II.)
• Title not available (Why is that?)
• An introduction to Kolmogorov complexity and its applications
• The measure theory of random fractals
• On non-computable functions
• Title not available (Why is that?)
• Complexity and randomness
• Title not available (Why is that?)
• Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
• Frontier between decidability and undecidability: A survey
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Title not available (Why is that?)
• Correspondence principles for effective dimensions
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Irreducibility and computational equivalence. 10 years after Wolfram's a new kind of science
• Small fast universal Turing machines
• ∑1-Density and Turing Degrees
• On Sets of Fractional Dimensions (III)
• Computability of Julia sets

Cited In (3)

• Nonlocal fractal neutrons transport equation and its implications in nuclear engineering
• Average Hewitt-Stromberg and box dimensions of typical compact metric spaces
• Title not available (Why is that?)

Uses Software

• Wolfram Demonstrations

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)