![](/images/graphics-bg.png)
Fractal Dimension versus Process Complexity
Joint Authors
Joosten, Joost J.
Soler-Toscano, Fernando
Zenil, Hector
Source
Advances in Mathematical Physics
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-21, 21 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-09-07
Country of Publication
Egypt
No. of Pages
21
Main Subjects
Abstract EN
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 ( 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.
American Psychological Association (APA)
Joosten, Joost J.& Soler-Toscano, Fernando& Zenil, Hector. 2016. Fractal Dimension versus Process Complexity. Advances in Mathematical Physics،Vol. 2016, no. 2016, pp.1-21.
https://search.emarefa.net/detail/BIM-1095844
Modern Language Association (MLA)
Joosten, Joost J.…[et al.]. Fractal Dimension versus Process Complexity. Advances in Mathematical Physics No. 2016 (2016), pp.1-21.
https://search.emarefa.net/detail/BIM-1095844
American Medical Association (AMA)
Joosten, Joost J.& Soler-Toscano, Fernando& Zenil, Hector. Fractal Dimension versus Process Complexity. Advances in Mathematical Physics. 2016. Vol. 2016, no. 2016, pp.1-21.
https://search.emarefa.net/detail/BIM-1095844
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1095844