![]() |
In this text I study the asymptotics of the complexity function of minimal multidimensional subshifts of finite type through their entropy dimension, a topological invariant that has been introduced in order to study zero entropy dynamical systems. Following a recent trend in symbolic dynamics I approach this using concepts from computability theory. In particular it is known [
Citation: |
Figure 33. Illustration of the correspondance between patterns of Figure 31 and parts of a supertile
Table 1. Correspondence table for positions on the border of a face
![]() |
Table 2. Correspondence table for positions inside a face
![]() |
[1] |
N. Aubrun and M. Sablik, Multidimensional effective S-adic subshift are sofic, Unif. Distrib. Theory, 9 (2014), 7-29.
![]() ![]() |
[2] |
A. Ballier, Propriétés Structurelles, Combinatoires et Logiques des Pavages, PhD Thesis, Aix-Marseille Université, 2009.
![]() |
[3] |
B. Durand and A. Romashchenko, On the expressive power of quasiperiodic SFT, 42nd International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 83 (2017), 1-14.
![]() ![]() |
[4] |
B. Durand, L. A. Levin and A. Shen, Complex tilings, J. Symbolic Logic, 73 (2008), 593-613.
doi: 10.2178/jsl/1208359062.![]() ![]() ![]() |
[5] |
S. Gangloff and M. Sablik, Quantified block gluing, aperiodicity and entropy of multidimensional SFT, Journal d'Analyse Mathématique.
![]() |
[6] |
B. Grunbaum and G. C. Shepherd, Tilings and Patterns, W. H. Freeman and Company, New York, 1987.
![]() ![]() |
[7] |
M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math., 171 (2010), 2011-2038.
doi: 10.4007/annals.2010.171.2011.![]() ![]() ![]() |
[8] |
M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.
doi: 10.1007/s00222-008-0161-7.![]() ![]() ![]() |
[9] |
M. Hochman and P. Vanier, Turing degree spectra of minimal subshifts, Computer Science - Theory and Applications, Lecture Notes in Comput. Springer, Cham, 10304 (2017), 154-161.
doi: 10.1007/978-3-319-58747-9_15.![]() ![]() ![]() |
[10] |
U. Jung, J. Lee and K. Koh Park, Topological entropy dimension and directional entropy dimension for z2-subshifts, Entropy, 19 (2017), 13pp.
doi: 10.3390/e19020046.![]() ![]() ![]() |
[11] |
E. Jeandel and P. Vanier, Characterizations of periods of multidimensional shifts, Ergodic Theory Dynam. Systems, 35 (2015), 431-460.
doi: 10.1017/etds.2013.60.![]() ![]() ![]() |
[12] |
T. Meyerovitch, Growth-type invariants for zd subshifts of finite type and arithmetical classes of real numbers, Invent. Math., 184 (2011), 567-589.
doi: 10.1007/s00222-010-0296-1.![]() ![]() ![]() |
[13] |
M. L. Minsky, Computation: Finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967.
![]() ![]() |
[14] |
S. Mozes, Tilings, substitution systems and dynamical systems generated by them, J. Analyse Math., 53 (1989), 139-186.
doi: 10.1007/BF02793412.![]() ![]() ![]() |
[15] |
R. Pavlov and M. Schraudner, Entropies realizable by block gluing shifts of finite type, J. Anal. Math., 126 (2015), 113-174.
doi: 10.1007/s11854-015-0014-4.![]() ![]() ![]() |
[16] |
R. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.
doi: 10.1007/BF01418780.![]() ![]() ![]() |
The south west supertile of order two (left) and a representation of petals intersecting its support (right)
Correspondence between infinite supertiles and sub-patterns of a supertile of finite order
Schema of the proof. The separating line is colored gray
Illustration of the definition of the sets
Illustration of the construction of the functions
Decomposition of the pattern
The set
Illustration of the signal transformation in Meyerovitch's construction
Schema of the proof for the minimality property of
Orientation of the faces of a three-dimensional cell. The symbols
Simplified schema of the construction presented in this text. The cube represents a three-dimensional version of the cells observable in the Robinson subshift
Schema of the functional positions on the faces of a three-dimensional cell
Schema of the main rule for the orientation sublayer. The squares in the dashed areas are superimposed with the corresponding symbol. The large square at the center is the support petal immediately above in the hierarchy
Schematic illustration of the rule of the functional areas sublayer. Colors are used as a code for other illustrations
Pattern over the surface of a three-dimensional cell of order three in the functional areas sublayer. The arrows are oriented according to the fixed orientations of the face
Schemata of the transformation rules for the vertical addressing. On the two schemata on the left, the central petal has
Illustration for the main rule of the horizontal addressing sublayer. The central petals on the two schemata on the left have
Illustration for the active functional areas sublayer on a two-dimensional cell over the face of a three-dimensional cell, with
Notations for the faces of three-dimensional cells
Localization of the machine symbols on the bottom faces of the cubes, according to the direction
Schema of the inputs and outputs directions when inside the area (1) and on the border of the area (2, 3, 4, 5, 6)
Illustration of the standard rules (1)
Illustration of the standard rules (2)
Illustration of the propagation rule of the error signal, where are represented the empty tape, first machine and empty sides signals
Illustration of the transformation rules of the hierarchy bits when the grouping bit is
Illustration of the completion of the
Illustration of the completion of the arrows according to the error signal in the known part of the area, designated by a dashed rectangle
Schema of the proof for the minimality property of
Illustration of the convolutions rules
Possible orientations of four neighbor supertiles having the same order (1)
Possible orientations of four neighbor supertiles having the same order (2)
Possible orientations of four neighbor supertiles having the same order (3)
Illustration of the correspondance between patterns of Figure 31 and parts of a supertile