×

zbMATH — the first resource for mathematics

Effective closed subshifts in 1D can be implemented in 2D. (English) Zbl 1287.37012
Blass, Andreas (ed.) et al., Fields of logic and computation. Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday. Berlin: Springer (ISBN 978-3-642-15024-1/pbk). Lecture Notes in Computer Science 6300, 208-226 (2010).
Summary: In this paper we use fixed-point tilings to answer a question posed by M. Hochman [Invent. Math. 176, No. 1, 131–167 (2009; Zbl 1168.37002)] and show that every one-dimensional effectively closed subshift can be implemented by a local rule in two dimensions. The proof uses the fixed-point construction of an aperiodic tile set and its extensions.
For the entire collection see [Zbl 1194.03003].

MSC:
37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
37B15 Dynamical aspects of cellular automata
52C23 Quasicrystals and aperiodic tilings in discrete geometry
68Q80 Cellular automata (computational aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aubrun, N., Sablik, M.: personal communication (February 2010) (submitted for publication)
[2] Berger, R.: The Undecidability of the Domino Problem. Mem. Amer. Math. Soc. 66 (1966) · Zbl 0199.30802 · doi:10.1090/memo/0066
[3] Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. Springer, Heidelberg (1987) · Zbl 0970.03001
[4] Durand, B., Levin, L., Shen, A.: Complex Tilings. J. Symbolic Logic 73(2), 593–613 (2008) · Zbl 1141.03021 · doi:10.2178/jsl/1208359062
[5] Durand, B., Levin, L., Shen, A.: Local Rules and Global Order, or Aperiodic Tilings. Mathematical Intelligencer 27(1), 64–68 (2005) · Zbl 1066.52501 · doi:10.1007/BF02984815
[6] Durand, B., Romashchenko, A., Shen, A.: Fixed Point and Aperiodic Tilings. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 276–288. Springer, Heidelberg (2008) · Zbl 1161.68033 · doi:10.1007/978-3-540-85780-8_22
[7] Durand, B., Romashchenko, A., Shen, A.: Fixed point theorem and aperiodic tilings (The Logic in Computer Science Column by Yuri Gurevich). Bulletin of the EATCS 97, 126–136 (2009)
[8] Durand, B., Romashchenko, A., Shen, A.: Fixed-point tile sets and their applications. CoRR abs/0910.2415 (2009), http://arxiv.org/abs/0910.2415 · Zbl 1244.05049
[9] Gács, P.: Reliable Computation with Cellular Automata. J. Comput. Syst. Sci. 32(1), 15–78 (1986) · Zbl 0621.68038 · doi:10.1016/0022-0000(86)90002-4
[10] Gács, P.: Reliable Cellular Automata with Self-Organization. J. Stat. Phys. 103(1/2), 45–267 (2001) · Zbl 0973.68158 · doi:10.1023/A:1004823720305
[11] Grunbaum, B., Shephard, G.C.: Tilings and Patterns. W.H. Freeman & Co., New York (1986)
[12] Gurevich, Y., Koryakov, I.: A remark on Berger’s paper on the domino problem. Siberian Mathematical Journal 13, 319–321 (1972) · Zbl 0248.02053 · doi:10.1007/BF00971620
[13] Hochman, M.: On the dynamic and recursive properties of multidimensional symbolic systems. Inventiones mathematicae 176, 131–167 (2009) · Zbl 1168.37002 · doi:10.1007/s00222-008-0161-7
[14] Mozes, S.: Tilings, Substitution Systems and Dynamical Systems Generated by Them. J. Analyse Math. 53, 139–186 (1989) · Zbl 0745.52013 · doi:10.1007/BF02793412
[15] von Neumann, J.: Theory of Self-reproducing Automata. In: Burks, A. (ed.). University of Illinois Press, Urbana (1966)
[16] Rumyantsev, A., Ushakov, M.: Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 396–407. Springer, Heidelberg (2006) · Zbl 1136.68473 · doi:10.1007/11672142_32
[17] Wang, H.: Proving theorems by pattern recognition II. Bell System Technical Journal 40, 1–42 (1961) · doi:10.1002/j.1538-7305.1961.tb03975.x
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.