Fractal dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal Dimension versus Computational Complexity Joost J. Joosten Fernando Soler-Toscano Hector Zenil jjoosten@ub.edu, fsoler@us.es, hectorz@labores.eu Seminari Cuc, Barcelona January, 2014 Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama The small Turing Machine database Small Turing machines We consider Turing machines where the tape extends infinitely in one direction (to the left in the diagrams) Each tape cell contains one symbol (color) We use just two colors: black and white A Turing machine starts its computation with the head at the first tape cell (beginning of the tape) The input of the computation is written at the initial cells The computation ends when the machine is at the beginning of the tape and moves to the right (out of the tape) The tape configuration upon termination of a computation is called the output The set of Turing machines with n states and k colors is represented by (n, k) We have enumerated the machines in (n, k) from 0 to (2 · n · k)n·k − 1 We present the results of an exhaustive study of (2, 2) and (3, 2) Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama The small Turing Machine database Space-time diagrams A space-time diagram for some computation is the joint collection of consecutive memory configurations The top-row of each diagram represents the input (1 to 14) The computation starts with the head of the TM in state 1 in the rightmost cell Each lower row represents the tape configuration of a next step in the computation These space-time diagrams define spatial objects by focussing on the black cells. We can measure the geometrical complexity. We wish to see if there is a relation between this geometrical complexity and the computational complexity (space or time usage) of the TM in question. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimensions Box dimension The notion of Box dimension is a simplification of, and an upper bound to Hausdorff dimension Suppose we have a mathematical object S of bounded size. The idea is to cover S with boxes in Rn and estimate the “volume” V(S) of S as function of the total number of boxes N(S, r) of size r needed to cover S: V(S) = limr↓0 rd N(S, r) Definition (Box dimension) Let S be some spatial object that can be embedded in some Rn , let N(S, r) denote the minimal number of boxes of size r needed to fully cover S. The Box dimension of S is denoted by δ(S) and is defined by δ(S) := lim r↓0 log(N(S, r)) log( 1 ) r in case this limit is well defined. In all other cases we shall say that δ(S) is undefined. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimensions Box dimension for Space-Time diagrams We adapt the notion of Box dimension to space-time diagrams Clearly, for each input on which the TM halts the corresponding space-time diagram has dimension 2: it’s a piece of surface It gets interesting when we consider limiting behavior of the TM Definition (Box dimension of a Turing machine) Let τ be a TM that converges on infinitely many input values x. In case τ(x) ↓, let N(τ, x) denote the number of black cells in the space-time diagram of τ on input x and let t(τ, x) denote the number of steps needed for τ to halt on x. We will define the Box dimension of a TM τ and denote it by d(τ). In case t(τ, x) is constant from some x onwards, we define d(τ) := 2. Otherwise, we define d(τ) := lim inf x→∞ Fractal Dimension versus Computational Complexity log N(τ, x) log t(τ, x) .

Box dimension and Turing machines The experiment Demo Theoretical panorama The Space-Time Theorem and applications The Space-time Theorem: upper and lower bounds Theorem (Space-time Theorem: upper bound) Let us, for a given TM τ, denote by s(x) the number of cells visited by τ on input x, and let t(x) denote the number of computation steps it took τ to terminate on input x. If lim infx→∞ log(s(x)) log(t(x)) = n then d(τ) ≤ 1 + n. Lemma (lower bound) For each TM τ we have that d(τ) ≥ 1 provided limx→∞ Fractal Dimension versus Computational Complexity s(x) t(x) = 0.

Box dimension and Turing machines The experiment Demo Theoretical panorama The Space-Time Theorem and applications The Upper Bound Conjecture Lemma In case a TM τ uses polynomial space, and runs super-polynomial time we have that d(τ) = 1. More in general, if τ uses space sτ (x) and time tτ (x) on input x then lim inf log sτ (x) x→∞ log tτ (x) = 0 ⇐⇒ d(τ) = 1. Conjecture (Upper Bound Conjecture) We conjecture that for each n ∈ ω and each TM τ in (n, 2) space that d(τ) = 1 + lim inf x→∞ Fractal Dimension versus Computational Complexity log sτ (x) log tτ (x)

Box dimension and Turing machines The experiment Demo Theoretical panorama The Space-Time Theorem and applications The Space-Time Theorem and P versus NP Using the previous Lemma, we can state a separation of P and NP in terms of dimensions: Let Π be some NP-complete problem If for each PSPACE Turing machine τ that decides Π we have that d(τ) = 1, then P NP. Clearly, this does not constitute a real strategy since, in general, it is undecidable whether d(τ) = 1 Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Methodology Slow convergence Our aim is to use computer experiments to compute the Box dimension of all TMs τ where d(τ) is not predicted by any theoretical result. A substantial complication is caused by the occurrence of logarithms in d(τ) As a consequence, increase in precision of d(τ) requires exponentially larger inputs For (2, 2) TM 346 we know that its Box dimension is 2, but we can see in the picture how slow the rate of convergence is Our way out here is to apply numerical and mathematical analysis to the functions involved so that we can retrieve their limit behavior. We are interested in three diﬀerent functions: tτ (x), number of time-steps needed for τ to halt on input x Nτ (x), number of black cells in the space-time diagram of τ on input x sτ (x), number of tape cells visited by τ on input x Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Methodology Steps followed Each TM in (2, 2) also occurs in (3, 2) so for the ﬁnal results it suﬃces to focus on this data-set. We isolated the TMs for which there is no theorem that predicts the corresponding dimension. Boxes O(n3 ) O(n4 ) o(P) Runtime O(n2 ) O(n3 ) o(P) Space O(n) O(n) o(P) Machines 3358 6 14 Per TM τ, we determined its functions sτ (x) (space), tτ (x) (time) and Nτ (x) (black cells). We used FindSequenceFunction and other Mathematica functions Per TM τ, we computed its dimension d(τ) as log(N (x)) d(τ) = lim infx→∞ log(tττ(x)) Per TM τ, we compared its dimension d(τ) to its theoretical log(sτ (x)) upper bound 1 + lim infx→∞ log(tτ (x)) Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Methodology Alternating convergent behavior Some machines have alternating asymptotic behavior This is the most extreme example (TM 1,728,529): For convenience we have changed the orientation of the diagrams so that time ‘goes from left to right’ instead of from ‘top to bottom’. In a sense this TM incorporates two diﬀerent algorithms to compute this output: one in linear time, the other, in exponential time. We have found alternating sequences of periodicity 2, 3 and 6 The periodicity typically reﬂects either the number of states, the number of colors, or a divisor of their product. Because of this alternating behavior we could not analyze the data in a straight-forward automated fashion. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Findings in (2, 2) space In (2, 2) there was a total of 74 diﬀerent functions. Only 5 of them where computed by some super-linear time TMs In total, in (2, 2) space, there are only 7 TMs that run in super-polynomial time. Three of them run in exp-time, all computing the tape-identity. The other four (see below) TMs compute diﬀerent functions (that roughly double the tape input) All these four TMs perform in quadratic time and linear space. The dimension for these functions is 3 . This is exactly the upper 2 bound as predicted by the Space-Time Theorem. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Findings in (3, 2) space The (3, 2) space contains 2,985,984 many diﬀerent TMs which compute 3,886 diﬀerent functions Almost all TMs used at most linear space for their computations The only exception to this was when the TM used exponential space Busy Beaver: we call a TM β a Busy Beaver whenever for each TM τ, there is some value x0 so that for all x ≥ x0 we have tβ (x) ≥ tτ (x) Twin Machines 599,063 and 666,364 are the Busy Beavers in (3,2) space, running in exponential space and time. They compute the largest runtime, space and boxes sequences. They also produce the longest output strings. Fractal dim.: 3/2 Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment The space-time theorem revisited One of our most important empirical ﬁndings is that the upper bound as given by the Space-Time Theorem is actually always attained in (3, 2) space. Finding 1 For all TMs τ in (3,2) space we found that d(τ) = 1 + lim inf x→∞ log(sτ (x)) log(tτ (x)) as conjectured in the Upper Bound Conjecture (UBC postulates this for any number of states). Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Other findings Finding 2 For all TMs τ in (3,2) space we found that d(τ) = 1 if and only if the TM ran in super-polynomial time using polynomial space. We suspect that this equivalence holds no longer true in higher spaces, i.e., spaces (n, 2) for n > 3. Finding 3 For all TMs τ in (3,2) space we found that d(τ) = 2 if and only if the TM ran in at most linear time. It is unknown if this equivalence holds true in higher spaces (the “if” part holds in general and is proven previous lemmas) Finding 4 s(x) For all TMs τ in (3,2) space we found that limx→∞ t(x) = 1 so that d(τ) ≥ 1. We conjecture this holds true also in larger space. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Richness in the (3, 2) space We have found two symmetric performers for even inputs This can only occur in machines computing the tape identity and requires strong conditions It is surprising that such constraints can be met in (3, 2) Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Part of a larger project H. Zenil, F. Soler-Toscano, J. J. Joosten. Empirical Encounters with Computational Irreducibility and Unpredictability. Minds & Machines, Volume 22, Issue 3, pages 149-165, 2012. J. J. Joosten, F. Soler, and H. Zenil. Program-size versus Time Complexity. Slowdown and Speed-up Phenomena in the Micro-cosmos of Small Turing Machines. Int. Journ. of Unconventional Computing, Vol. 7, pp. 353-387, 2011. Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil. Fractal Dimension of Space-time Diagrams and the Runtime Complexity of Small Turing Machines, in T. Neary and M. Cook (Eds.): Machines, Computations and Universality (MCU 2013). J. J. Joosten. Complexity, Universality and Intermediate Degrees. In American Institute of Physics Conference proceedings, Volume 1479, Pages 638-641, AIP Publishing, ISSN 0094 243X, doi:http://dx.doi.org/10.1063/1.4756215, 2012. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Part of a larger project J. J. Joosten, F. Soler-Toscano, and H. Zenil. Complejidad ´ ˜ descriptiva y computacional en maquinas de Turing pequenas. Proceedings of the V Jornadas Ib´ ricas de Filosof´a de la Ciencia, e ı Logica y Lenguaje, Lisbon 2010, in Logica Universal e Unidade ´ ´ da Ciˆ ncia, Centro de Filosoﬁa das Ciˆ ncias da Universidade de e e Lisboa, pp. 11-32, ISBN: 978-989-8247-49-0, 2011. J. J. Joosten, F. Soler-Toscano, H. Zenil. Speedup and Slowdown Phenomena in Turing Machines. Wolfram Demonstrations Project, http://demonstrations.wolfram.com/ SpeedupAndSlowdownPhenomenaInTuringMachines/, 2012. J. J. Joosten. Turing Machine Enumeration: NKS versus Lexicographical. Wolfram Demonstrations Project, http://demonstrations.wolfram.com/ TuringMachineEnumerationNKSVersusLexicographical/, 2010. J. J. Joosten, F. Soler-Toscano, H. Zenil. Runtime complexity of small Turing Machines and fractal dimension. Wolfram Demonstrations Project, To be submitted soon, 2014. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Most salient results of the experiment Part of a larger project J. J. Joosten, H. Zenil, F. Soler-Toscano. Entropy as an indication of the runtime of terminating discrete dynamical processes. In Book of abstracts, European Conference on Complex Systems, p214, S. Thurner M. Szell editors, Locker Verlag, ISBN ¨ 978-3-85409-613-9, Vienna 2011. J. J. Joosten. Complexity ﬁts the ﬁttest. In Emergence, Complexity and Computation in Nature. Springer Verlag, I. Zelinka, A. Sanayei, H. Zenil H., O. E. Rossler, editors, ISBN 978-3-319-00253-8, 2013. J. J. Joosten. On the Necessity of Complexity. In Irreducibility and Computational Equivalence: 10 Years After the Publication of Wolfram’s A New Kind of Science, (11-24). Springer, Heidelberg New York Dordrecht London, H. Zenil editor, ISBN 978-3-642-35481-6, 2013. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Demo We have prepared a demo to visualize the space-time diagrams for several TMs in (3, 2) It will be published in Wolfram Demonstrations Project, and is available upon request Fractal Dimension versus Computational Complexity

Box dimension and Turing machines Demo Fractal Dimension versus Computational Complexity The experiment Demo Theoretical panorama

Box dimension and Turing machines The experiment Demo Theoretical panorama Complexity measures related Various complexity measures Entropy, box-counyting dimension, computational complexity, Kolmogorov complexity, Hausdorff dimension, etc. Each such measure captures/quantifies (or aims to) the complexity of one particular aspect of a system On philosophical grounds we can expect relations between different complexity measures J. J. Joosten. Complexity fits the fittest. In Emergence, Complexity and Computation in Nature. Springer Verlag, I. Zelinka, A. Sanayei, H. Zenil H., O. E. Rossler, editors, ISBN 978-3-319-00253-8, 2013. J. J. Joosten. On the Necessity of Complexity. In Irreducibility and Computational Equivalence: 10 Years After the Publication of Wolfram’s A New Kind of Science, (11-24). Springer, Heidelberg New York Dordrecht London, H. Zenil editor, ISBN 978-3-642-35481-6, 2013. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures Topological dimensions Edgar divides geometrical dimensions in two main groups, topologic versus fractal dimension. Edgar E. G. Measure, Topology, and Fractal Geometry, Springer-Verlag. New York, 1990. Most basic of all topological dimensions is cover dimension also called Lebesgue dimension. The order of a family A of sets is ≤ n by deﬁnition when any n + 2 of the sets have empty intersection. We say = n when ≤ n but not ≤ n − 1. The cover dimension of a set S is n –we write Cov(S) = n– whenever each open covering of S has a reﬁnement of order n. Topological measures have integer values and are invariant under homeomorphisms. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures Fractal dimensions A fractal dimension of some object S is an indication of how close S is to some integer-valued dimensional space Dimension in integer-valued dimensional space in a sense express degrees of freedom (information theoretical focus) Falconer: “Roughly, dimension indicates how much space a set occupies near to each of its points.” (geometrical focus) Falconer, K. J. Fractal Geometry, Mathematical Foundations and Applications, Wiley, Chichester, 2003. Most fundamental, and most common notion is that of Hausdorff dimension ¨ F. Hausdorff Dimension und ausseres Mass. Mathematische Annalen, 79:157–179, 1919. ¨ Building upon ideas of Carath´ odory: Carath´ odory, C. Uber das e e lineare Mass von Punktmengen, eine Veralgemeinerung des ¨ Langenbegriffs. Nachrichten von der Wissenschaften zu Gotingen, Mathematisch-Physikalische Klass, 404–426, 1914. ¨ Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures Hausdorff dimension For a S some subset of some metric space we can consider countable open coverings A of S and define (diam A)s . s Hε (S) := inf A∈A The infimum is taken over all A that are countable open ε-covers of S. Then s H s (S) := lim Hε (S). ε→0 Main Theorem: There is a unique s so that t Hε (S) = ∞ for t < s; t Hε (S) = 0 for t > s. This unique s is called the Hausdorff (Mandelbrot speaks of Hausdorff-Besicovitch) dimension of S: dimH (F). Besicovitch, A. S. Sets of fractional dimensions. Part I: Mathematical Annals 101, 161–193, 1929. Part V: London Mathematical Society 12, 18–25, 1934. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures Packing dimension Hausdorff comes with a natural dual dimension called packing dimension. Tricot, C. Jr. Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, 91, 57–74, 1982. Sullivan, D. Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Mathematica, 153, 259–277, 1984. |Bi | | {Bi }i are disjoint balls at radii ≤ δ and center in F} Ps (F) := {sup δ i Since limδ→0 Ps (F) is not a measure (consider countable dense δ sets) one defines ∞ Ps (F) := inf{ {Fi }i Fractal Dimension versus Computational Complexity lim Ps (Fi ) | F ⊆ δ i δ→0 Fi }. i=1

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures Main Theorem: There is a unique s so that Pt (F) = 0 for t < s; ε t Hε (S) = ∞ for t > s. This unique s is called the packing dimension of F: dimP (F). Packing dimension is an upper bound to Hausdorﬀ dimension: dimH (F) ≤ dimP (F) A fundamental property: Cov(F) ≤ dimH (F) Mandelbrot deﬁnes a fractal for any set F with Cov(F) < dimH (F) Often considered (also by Mandelbrot) a notion of fractal that is too broad, since it admits “true geometric chaos” J. Taylor proposes to denote by fractals only Borel sets F for which dimH (F) ≤ dimP (F). Taylor, S. J. The measure theory of random fractals. Mathematical Proceedings of the Cambridge Philosophical Society, 100, 383–406, 1986. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures Box dimensions The Box dimension is like Hausdorff dimension only that we now cover by balls/boxes of fixed size. Alternatively and equivalently, divide space into a regular mesh with mesh-size δ and count how many cells Nδ (F) are hit by a set F Then define Bs (F) := Nδ (F)δs and Bs (F) := lim infδ→0 Nδ (F)δs . δ Again, there is a cut-off value s0 so that Bs (F) = ∞ for s < s0 and Bs (F) = 0 for s > s0 This cut-off value is given by lim inf δ→0 log(Nδ (F)) . log(1/δ) log(Nδ (F)) and δ→0 log(1/δ) log(Nδ (F)) dimB := lim sup log(1/δ) δ→0 We define dimB := lim inf Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures In case dimB (F) = dimB (F) we call this the box-counting dimension: dimB (F) Box dimension always provides an upper bound to Hausdorﬀ dimension Box dimension has desirable computational properties but undesirable mathematical properties: a countable union of measure zero sets can have positive box dimension Example: dimB {0, 1 , 1 , 1 , . . .} = 2 3 4 1 2 Mathematically this can be repaired by deﬁning ∞ dimMB (F) := inf{sup dimB (Fi ) | F ⊆ {Fi } i Fi } and i=1 ∞ dimMB (F) := inf{sup dimB (Fi ) | F ⊆ {Fi } i Fi } i=1 loosing the good computational properties of course . . . Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Geometrical complexity measures We have dimH (F) ≤ dimMB (F) ≤ dimMB (F) = dimP (F) ≤ dimB (F) None of the inequalities can be replaced by equalities Note that under Taylor’s definition of fractal, the first four dimensions collapse and modified box dimension is an equivalent of Hausdorff dimension Moreover, if F has a lot of self-similarity, then modified is equal to plane box counting dimension: Let F ⊆ R be compact so that for any open set V we have dimB (F) = dimB (F ∩ V), then dimB (F) = dimMB (F). So in various situations, box counting coincides with Hausdorff dimension (like Mandelbrot set) There are various other situations where box-counting and Hausdorff dimension coincide Staiger, L. A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory of Computing Systems, 31:215–229, 1998. Staiger, L. Constructive dimension equals Kolmogorov Complexity. Information Processing Letters, 93:149–153, 2005. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Computational properties of fractals Julia sets Probably the most famous examples of fractals are Julia sets and the corresponding “roadmap Mandelbrot set” By FJ(f ) we denote the ﬁlled Julia set of a function f deﬁned on the complex numbers is the set of values z in the domain of f on which iterating f on z does not diverge. That is, FJ(f ) := {z | lim sup |f n (z)| < ∞} n→∞ By J(f ) –the Julia set of f – we denote the boundary of FJ(f ) Following C.T. Chong, we can consider fθ (z) = z2 + λz with λ = e2πiθ and θ Q Corresponding Julia sets are denoted by Jθ Jθ being well-behaved is expressed by saying that it has a Siegel disk at z = 0 Basically, this says that f is locally linearizable at z = 0 by a rotation See: Milnor, J. Dynamics in one complex variable. Introductory lectures. Princeton University Press, 2006. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Computational properties of fractals Constructive Analysis There are various results between the Turing degree of θ and that of Jθ One first has to define what the Turing degree of non-discrete objects actually means Braverman and Yampolsky follow an approach of Constructive Analysis as initiated by Banach and Mazur, with influence of Markov. Banach, S., Mazur, S. Sur les fonctions calculables. Ann. Polon. Math. 16, 1937. Markov, A. A. On constructive mathematics (Russian) Tr. Mat. Inst. Steklov. 67, 8–14; translated in Amer. Math. Soc., Trans., II Ser. 98, 1–9, 1962. Overview: Weihrauch, Computable Analysis, Springer, Berlin, 2000. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Computational properties of fractals Computational properties of fractals Braverman, Yampolsky: b is a c.e. Turing degree if and only if it is the degree of Jθ with θ recursive so that Jθ has a Siegel disk Braverman, M., Yampolsky, M. Computability of Julia Sets, Algorithms and Computation in Mathematics, Springer, 2009. C.T. Chong Generalized this result: Let c be a Turing degree. For every d ≥ c we have that d is c.e. in c if and only if it is the degree of a Julia set Jθ with Siegel disk and deg(θ) = c. C.T. Chong, unpublished; Slides Complex Dynamics and Turing Degrees online. Results sensitive to model of computation and change with, e.g., Blum-Schub-Smale model See L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998. This relates the Turing complexity of the fractal to the complexity of the parameter generating it However, no link to the corresponding dimension This we will see in what follows Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimension versus other complexity notions Hausdorff dimension on strings Let us reformulate the definition of Hausdorff dimension in the realm of binary sequences, i.e., Cantor space Overview can be found in Downey, R.G. and Hirschfeldt, D.R. Algorithmic Randomness and Complexity, Chapter 13, Springer, 2010. For σ ∈ 2<ω we denote the length of σ as |σ| For σ ∈ 2<ω we define σ := {στ | τ ∈ 2ω } (a (sub-)basic open set) For Σ ⊆ 2<ω we define Σ := σ∈Σ σ Let R ⊆ 2ω . An n-cover of R is a set Σ ⊆ 2≥n so that R ⊆ Σ . 2−s|σ| | Σ an n-cover of R} s Hn (R) := inf{ σ∈Σ s H (R) := lim n→∞ s Hn (R) So, as before, dimH (R) := inf{s | H s (R) = 0} Clearly, for every r ∈ R there is R ⊆ 2ω with dimH (R) = r Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimension versus other complexity notions Effective Hausdorff dimension The effective pendant is now defined via EH s (R) := inf{ n 2−s|σ| | Σ a c.e. n-cover of R} σ∈Σ s EH (R) := lim n→∞ EHs (R) n So that the effective Hausdorff dimension is defined as dimEH (R) := inf{s | EH s (R) = 0} For every computable real r, there is a set R ⊆ 2ω with dimEH (R) = r. Lutz, J. H. The dimension of individual strings and sequences Information and Computation, 187:49–79, 2003. For important subsets F of Cantor space we have that dimH (F) = dimEH (F): Theorem[Hitchcock] Let F be a countable union of Π0 -definable 1 subsets of Cantor space, then dimH (F) = dimEH (F) Hitchcock, J.M. Correspondence principles for effective dimensions. Theory of Computing Systems, 38:559–571, 2005. Fractal Dimension versus Computationalan equality for Σ0 classes and computable Hausdorff Also proves Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimension versus other complexity notions Turing degrees and Hausdorff dimension Note that for A ∈ 2ω we have dimH (A) = 0. We can have dimEH (A) > 0. In a sense, having non-zero effective Hausdorff dimension is an indication of containing complexity Let A ∈ 2ω . If dimEH (A) > 0, then A can compute a non-recursive function. In particular, A can compute a fix-point free function f (that is, a function f so that Wf (e) We for all numbers e). Terwijn, S.A. Complexity and Randomness Rendiconti del Seminario Matematico di Torino, 62:1–38, 2004. Jockush Jr., C.G., Lerman, M., Soare, R. I., and Solovay, R.M. Recursively enumerable sets modulo iterated jumps and Arslanov’s completeness criterion. Journal of Symbolic Logic, 54:1288–1323, 1989. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimension versus other complexity notions The relation between effective dimension and computable content is not monotone nor simple. If dimEH (A) = α, then there exist sets B of arbitrary high Turing degree with dimEH (B) = α However locally, Hausdorff dimension can provide an upper bound to Turing degrees Let r be a left-c.e. real. There is a ∆0 -definable set R ∈ 2ω with 2 dimEH (R) = r so that moreover A ≤T R ⇒ dimEH (A) ≤ α. Miller, J. S. Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension. Advances in Mathematics. Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimension versus other complexity notions Kolmogorov complexity and Hausdorff dimension For a string s ∈ 2<ω the Kolmogorov complexity K(s) is roughly the length of the shortest program that outputs s when computed on a particular universal Turing machine Diﬀerent choices of a universal Turing machine only manifest itself in an additive constant in K K(A n) . n E. Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorﬀ dimension. Information Processing Letters, 84:1–3, 2002. dimEH (A) = lim inf n→∞ Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Fractal dimension versus other complexity notions Hausdorff dimension and probability Martingales are central to probability theory and indicate expected outcomes of betting strategies Lutz: An s-gale is a function d : 2<ω → R≥0 such that d(σ0)+d(σ1) d(σ) = 2s d(σ0)+d(σ1) This is a generalization of ‘gales’ (Levy) where d(σ) = 2 expresses a certain fairness condition of the betting strategy. We say that d succeeds on A whenever lim supn→∞ d(A n) = ∞ The Success set of d is the collection of all A on which d succeeds and is denoted by S[d] Lutz: dimEH (X) = inf{q ∈ Q | X ⊆ S[d] for some q-gale d} Fractal Dimension versus Computational Complexity

Box dimension and Turing machines The experiment Demo Theoretical panorama Our result in this landscape Our result Is new in that it relates geometrical complexity of object generated by TM to the runtime complexity of the TM All work so far dealt with Turing (or other) degrees instead of runtime complexity Also, we have discrete geometrical objects for which we consider the (limiting) geometrical dimension Fractal Dimension versus Computational Complexity

Fractal dimension versus Computational Complexity

More Related Content

What's hot

Viewers also liked

Similar to Fractal dimension versus Computational Complexity

More from Hector Zenil

Recently uploaded

Fractal dimension versus Computational Complexity