Fractal Dimension versus Process Complexity

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 τ and any particular input x, we consider what we call the space-time diagram which is basically the collection of consecutive tape configurations...

Full description

Saved in:
Bibliographic Details
Main Authors: Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil
Format: Article
Language:English
Published: Wiley 2016-01-01
Series:Advances in Mathematical Physics
Online Access:http://dx.doi.org/10.1155/2016/5030593
Tags: Add Tag
No Tags, Be the first to tag this record!
_version_ 1832562990134591488
author Joost J. Joosten
Fernando Soler-Toscano
Hector Zenil
author_facet Joost J. Joosten
Fernando Soler-Toscano
Hector Zenil
author_sort Joost J. Joosten
collection DOAJ
description 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 τ 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 τ(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 O(xn), 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.
format Article
id doaj-art-ffde989bd56d4d6f9d80bcbe25fbca8d
institution Kabale University
issn 1687-9120
1687-9139
language English
publishDate 2016-01-01
publisher Wiley
record_format Article
series Advances in Mathematical Physics
spelling doaj-art-ffde989bd56d4d6f9d80bcbe25fbca8d2025-02-03T01:21:27ZengWileyAdvances in Mathematical Physics1687-91201687-91392016-01-01201610.1155/2016/50305935030593Fractal Dimension versus Process ComplexityJoost J. Joosten0Fernando Soler-Toscano1Hector Zenil2Departamento de Lògica, Història i Filosofia de la Ciéncia, Universitat de Barcelona, 08001 Barcelona, SpainAlgorithmic Nature Group, LABORES, 75006 Paris, FranceAlgorithmic Nature Group, LABORES, 75006 Paris, FranceWe 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 τ 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 τ(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 O(xn), 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.http://dx.doi.org/10.1155/2016/5030593
spellingShingle Joost J. Joosten
Fernando Soler-Toscano
Hector Zenil
Fractal Dimension versus Process Complexity
Advances in Mathematical Physics
title Fractal Dimension versus Process Complexity
title_full Fractal Dimension versus Process Complexity
title_fullStr Fractal Dimension versus Process Complexity
title_full_unstemmed Fractal Dimension versus Process Complexity
title_short Fractal Dimension versus Process Complexity
title_sort fractal dimension versus process complexity
url http://dx.doi.org/10.1155/2016/5030593
work_keys_str_mv AT joostjjoosten fractaldimensionversusprocesscomplexity
AT fernandosolertoscano fractaldimensionversusprocesscomplexity
AT hectorzenil fractaldimensionversusprocesscomplexity