×

Fractal dimension versus process complexity. (English) Zbl 1401.68078

Summary: We look at small Turing machines (TMs) that work with just two colors (alphabet symbols) and either two or three states. For any particular such machine \(\tau\) and any particular input \(x\), we consider what we call the space-time diagram which is basically the collection of consecutive tape configurations of the computation \(\tau(x)\). In our setting, it makes sense to define a fractal dimension for a Turing machine as the limiting fractal dimension for the corresponding space-time diagrams. 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, if and only if its dimension is 2, and its dimension is 1, if and only if it runs in superpolynomial time and it uses polynomial space. If a TM runs in time \(\mathcal{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 one side versus the time complexity of a computation on the other side.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
28A80 Fractals
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Zenil, H., Compression-based investigation of the dynamical properties of cellular automata and other systems, Complex Systems, 19, 1, 1-28 (2010) · Zbl 1217.68145
[2] Zenil, H.; Villarreal, E., Asymptotic behaviour and ratios of complexity in cellular automata rule spaces, International Journal of Bifurcation and Chaos, 23, 9, 13-19 (2013)
[3] Solomonoff, R. J., A formal theory of inductive inference. II, Information and Computation, 7, 224-254 (1964) · Zbl 0259.68038
[4] Zvonkin, A. K.; Levin, L. A., The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms, Russian Mathematical Surveys, 25, 6, 85-127 (1970) · Zbl 0222.02027
[5] Bennett, C. H., Logical depth and physical complexity, The Universal Turing Machine: A Half-Century Survey, 227-257 (1988), Oxford University Press · Zbl 0668.03017
[6] Zenil, H.; Soler-Toscano, F.; Delahaye, J.; Gauvrit, N., Two-dimensional Kolmogorov complexity and an empirical validation of the coding theorem method by compressibility, PeerJ Computer Science, 1, article e23 (2015) · doi:10.7717/peerj-cs.23
[7] Chaitin, G. J.; Cover, T. M.; Gopinath, B., Computing the busy beaver function, Open Problems in Communication and Computation, 108-112 (1987), New York, NY, USA: Springer, New York, NY, USA · doi:10.1007/978-1-4612-4808-8_28
[8] Zenil, H., On the dynamic qualitative behaviour of universal computation, Complex Systems, 20, 3, 265-277 (2012)
[9] Krakover, S., Spatio-temporal structure of population growth in urban regions: the cases of Tel-Aviv and Haifa, Israel, Urban Studies, 22, 4, 317-328 (1985) · doi:10.1080/00420988520080551
[10] Vicsek, T., Fractal Growth Phenomena (1989), Singapore: World Scientific, Singapore · Zbl 0744.28005 · doi:10.1142/0511
[11] Feng, J.; Chen, Y. G., Spatiotemporal evolution of urban form and land-use structure in Hangzhou, China: evidence from fractals, Environment and Planning B: Planning and Design, 37, 5, 838-856 (2010) · doi:10.1068/b35078
[12] Wolfram, S., A New Kind of Science (2002), Wolfram Media · Zbl 1022.68084
[13] Joosten, J. J., Turing machine enumeration: NKS versus lexicographical
[14] Joosten, J. J.; Soler-Toscano, F.; Zenil, H., Program-size versus time complexity slowdown and speed-up phenomena in the micro-cosmos of small turing machines, International Journal of Unconventional Computing, 7, 5, 353-387 (2011)
[15] Neary, T.; Woods, D., Small fast universal Turing machines, Theoretical Computer Science, 362, 1-3, 171-195 (2006) · Zbl 1100.68027 · doi:10.1016/j.tcs.2006.06.002
[16] Margenstern, M., Frontier between decidability and undecidability: a survey, Theoretical Computer Science, 231, 2, 217-251 (2000) · Zbl 0956.03041 · doi:10.1016/S0304-3975(99)00102-4
[17] Hausdorff, F., Dimension und äusseres mass, Mathematische Annalen, 79, 157-179 (1919) · JFM 46.0292.01
[18] Tadaki, K., The Hausdorff dimension of the halting self-similar sets of T-universal prefix-free machines, Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT ’10), IEEE · doi:10.1109/isit.2010.5513715
[19] Zenil, H.; Soler-Toscano, F.; Joosten, J. J., Empirical encounters with computational irreducibility and unpredictability, Minds and Machines, 22, 3, 149-165 (2012) · doi:10.1007/s11023-011-9262-y
[20] Joosten, J. J.; Soler-Toscano, F.; Zenil, H., Fractal Dimension versus Time Complexity in Turing Machines (2014), Wolfram Demonstrations Project
[21] Rado, T., On non-computable functions, The Bell System Technical Journal, 41, 3, 877-884 (1962) · Zbl 1497.68176 · doi:10.1002/j.1538-7305.1962.tb00480.x
[22] Joosten, J. J.; Zenil, H., On the necessity of complexity, Irreducibility and Computational Equivalence: 10 Years After the Publication of Wolfram’s A New Kind of Science, 11-24 (2013), New York, NY, USA: Springer, New York, NY, USA · Zbl 1263.68024
[23] Joosten, J. J.; Zelinka, I.; Sanayei, A.; Zenil, H.; Rössler, O. E., Complexity fits the fittest, How Nature Works. How Nature Works, Emergence, Complexity and Computation, 5, 51-63 (2014), Berlin, Germany: Springer, Berlin, Germany · doi:10.1007/978-3-319-00254-5_3
[24] Edgar, G. A., Measure, Topology, and Fractal Geometry (1990), New York, NY, USA: Springer, New York, NY, USA · Zbl 0727.28003 · doi:10.1007/978-1-4757-4134-6
[25] Falconer, K. J., Fractal Geometry, Mathematical Foundations and Applications (2003), Chichester, UK: John Wiley & Sons, Chichester, UK · Zbl 1060.28005
[26] Carathéodory, C., Über das lineare mass von punktmengen, eine veralgemeinerung des längenbegriffs, Nachrichten von der Wissenschaften zu Götingen, Mathematisch-Physikalische Klass, 404-426 (1914) · JFM 45.0443.01
[27] Besicovitch, A. S., On linear sets of points of fractional dimension, Mathematische Annalen, 101, 1, 161-193 (1929) · JFM 55.0747.01 · doi:10.1007/BF01454831
[28] Besicovitch, A. S., On the sum of digits of real numbers represented in the dyadic system. On sets of fractional dimensions II, Mathematische Annalen, 110, 1, 321-330 (1935) · Zbl 0009.39503 · doi:10.1007/bf01448030
[29] Besicovitch, A. S., Sets of fractional dimensions. Part III, London Mathematical Society, s2-47, 436-454 (1942) · Zbl 0028.35102
[30] Besicovitch, A. S., Sets of fractional dimensions (IV): on rational approximation to real numbers, Journal of the London Mathematical Society, s1-9, 2, 126-131 (1934) · Zbl 0009.05301 · doi:10.1112/jlms/s1-9.2.126
[31] Besicovitch, A. S.; Ursell, H. D., Sets of fractional dimensions (V): on dimensional numbers of some continuous curves, Journal of the London Mathematical Society, s1-s12, 1, 18-25 (1937) · Zbl 0016.01703 · doi:10.1112/jlms/s1-12.45.18
[32] Tricot, C., Two definitions of fractional dimension, Mathematical Proceedings of the Cambridge Philosophical Society, 91, 1, 57-74 (1982) · Zbl 0483.28010 · doi:10.1017/s0305004100059119
[33] Sullivan, D., Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups, Acta Mathematica, 153, 3-4, 259-277 (1984) · Zbl 0566.58022 · doi:10.1007/BF02392379
[34] Taylor, S. J., The measure theory of random fractals, Mathematical Proceedings of the Cambridge Philosophical Society, 100, 3, 383-406 (1986) · Zbl 0622.60021 · doi:10.1017/S0305004100066160
[35] Staiger, L., A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory of Computing Systems, 31, 3, 215-229 (1998) · Zbl 0896.68080 · doi:10.1007/s002240000086
[36] Staiger, L., Constructive dimension equals Kolmogorov complexity, Information Processing Letters, 93, 3, 149-153 (2005) · Zbl 1173.68542 · doi:10.1016/j.ipl.2004.09.023
[37] Chong, C. T., Complex dynamics and turing degrees · Zbl 0636.03038
[38] Milnor, J., Dynamics in One Complex Variable. Introductory Lectures (2006), Princeton, NJ, USA: Princeton University Press, Princeton, NJ, USA · Zbl 1085.30002
[39] Braverman, M.; Yampolsky, M., Computability of Julia sets. Computability of Julia sets, Algorithms and Computation in Mathematics, 23 (2009), Berline, Germany: Springer, Berline, Germany · Zbl 1314.37033
[40] Banach, S.; Mazur, S., Sur les fonctions calculables, Annales Polonici Mathematici, 16, 223 (1937)
[41] Markov, A. A., On constructive mathematics, Akademiya Nauk SSSR. Trudy Matematicheskogo Instituta imeni V. A. Steklova, 67, 8-14 (1962)
[42] Weihrauch, K., Computable Analysis (2000), Berlin, Germany: Springer, Berlin, Germany · Zbl 0956.68056 · doi:10.1007/978-3-642-56999-9
[43] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), New York, NY, USA: Springer, New York, NY, USA · doi:10.1007/978-1-4612-0701-6
[44] Downey, R. G.; Hirschfeldt, D. R., Algorithmic Randomness and Complexity. Algorithmic Randomness and Complexity, Theory and Applications of Computability (2010), New York, NY, USA: Springer, New York, NY, USA · Zbl 1221.68005 · doi:10.1007/978-0-387-68441-3
[45] Lutz, J. H., The dimensions of individual strings and sequences, Information and Computation, 187, 1, 49-79 (2003) · Zbl 1090.68053 · doi:10.1016/s0890-5401(03)00187-1
[46] Hitchcock, J. M., Correspondence principles for effective dimensions, Theory of Computing Systems, 38, 5, 559-571 (2005) · Zbl 1084.68054 · doi:10.1007/s00224-004-1122-1
[47] Terwijn, S. A., Complexity and randomness, Rendiconti del Seminario Matematico di Torino, 62, 57-74 (2004) · Zbl 1121.68058
[48] Jockusch, J.; Lerman, M.; Soare, R. I.; Solovay, R. M., Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion, The Journal of Symbolic Logic, 54, 4, 1288-1323 (1989) · Zbl 0708.03020 · doi:10.2307/2274816
[49] Miller, J. S., Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Advances in Mathematics, 226, 1, 373-384 (2011) · Zbl 1214.03030 · doi:10.1016/j.aim.2010.06.024
[50] Li, M.; Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications (2008), New York, NY, USA: Springer, New York, NY, USA · Zbl 1185.68369 · doi:10.1007/978-1-4757-2606-0
[51] Mayordomo, E., A Kolmogorov complexity characterization of constructive Hausdorff dimension, Information Processing Letters, 84, 1, 1-3 (2002) · Zbl 1045.68570 · doi:10.1016/S0020-0190(02)00343-5
[52] Lutz, J. H., Gales and the constructive dimension of individual sequences, Automata, Languages and Programming: 27th International Colloquium, ICALP 2000 Geneva, Switzerland, July 9-15, 2000 Proceedings. Automata, Languages and Programming: 27th International Colloquium, ICALP 2000 Geneva, Switzerland, July 9-15, 2000 Proceedings, Lecture Notes in Computer Science, 1853, 902-913 (2000), Berlin, Germany: Springer, Berlin, Germany · Zbl 0973.68087 · doi:10.1007/3-540-45022-X_76
[53] Lévy, P., Théorie de l’Addition des Variables Aléatoires (1937), Paris, France: Gauthier-Villars, Paris, France · JFM 63.0490.04
[54] Reimann, J., Computability and fractal dimension [Ph.D. thesis] (2004), Universitä Heidelberg · Zbl 1080.03031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.