Closed problems

Here I list "open problems" that "I" have "solved".1

I usually work on my own problems rather than other people's, so this list is not necessarily representative of my research. Nevertheless I found it interesting to compile.

If you notice a mistake on this list (or in one of the results!), you can contact me through email. I know the reference list has very bad formatting, sorry about that.

Latest update: May 7th, 2021.

  1. Two mixing one-dimensional SFTs are conjugate if and only if they are conjugate without their periodic points.
  2. There is a group whose effective subshifts are sofic.
    • Asked in: [Aubrun-Barbieri-Sablik, 2017]
    • Our solution in: [Barbieri-Sablik-Salo, 2021]
    • Proof idea: In \(F_2\) you can find disjoint paths starting from each group element. So in \( F_2 \times F_2 \) you can have a separate grid for each group element. A simple geometric argument shows these grids can talk.
  3. The question of whether mapping class groups of mixing SFTs are sofic is not solvable at present.
    • Soficity of MCG is asked in: [Boyle-Chuysurichay, 2018]
    • Our reduction in: [Salo, 2021a]
    • Proof idea: Embed Thompson's \(V\). For this, biject dyadic rationals with finite words, have \(V\) act on them naturally. Perform this action between two markers.
  4. Every right-angled Artin group embeds in the Brin-Thompson \(2V\).
  5. The seeded tiling problem on the lamplighter group is undecidable.
    • Mentioned as open in a public research statement of Sebastián Barbieri. He did not remember asking it when I told him about the result, but I'm counting it anyway!
    • Our solution in: [Bartholdi-Salo, 2020]
    • Proof idea: Construct an SFT where every seeded configuration contains a gadget inside which a finite-state machine can interpret a grid. We construct two (geometrically rather different) such SFTs, the "comb" and the "sealevel".
  6. Conjugacy of reversible cellular automata is undecidable.
  7. Not all horoballs of finitely-generated groups are Busemann.
  8. Two-dimensional Turing machines can be topologically mixing in TMH.
    • We do not know if this question appears in the literature, but this was an open problem according to Anahí Gajardo.
    • Our solution in: [Salo-Törmä, 2020]
  9. Finite-support Gardens of Eden for Game of Life are a decidable set.
  10. Any ordinal can be realized as the CPE rank on a one-dimensional subshift.
    • Asked in private communication by Nishant Chandgotia.
    • Our solution in: [Salo, 2019a]
    • Westrick proves the analog for \(\mathbb{Z}^2\)-SFTs (confirming my conjecture from [Salo, 2019a]).
  11. Polygonal SFTs are not closed under conjugacy.
    • Asked in [Franks-Kra, 2020]; Pierre Guillon essentially asked it in a talk.
    • Our solution in: [Salo, 2019a]
    • Proof idea: Just recode Ledrappier, you can't fail.
  12. ECA 57 is a universal reversible logical gate.
    • Conjectured in: [Macauley-McCammond-Mortveit, 2011] and essentially in [Vielhaber, 2012].
    • Our solution in: [Salo, 2018a]
    • Proof idea: Construct the NOT gate by computer, then it's easy to find an existing universal gate set.
    • Note: The Toffoli gate seems beyond computer reach, so I don't have a human-free proof of the result. Probably could be done in GAP.
  13. Minimal subshifts can have the language pivot property.
    • Asked by Michael Hochman in the conference Current Trends in Dynamical Systems and the Mathematical Legacy of Rufus Bowen, organized in Vancouver in 2017.
    • Our solution in: [Salo, 2019]
    • Proof idea: Just do it / subshift construction from word concatenation.
  14. Settled the 11 remaining cases of Von Neumann regularity of elementary cellular automata.
  15. Quasiminimal subshifts can be trace universal.
  16. There exist strongly randomizing cellular automata.
  17. One-dimensional CA can be physically universal
    • Asked in [Schaeffer, 2014]
    • Our solution in: [Salo-Törmä, 2017]
    • Related: A physically universal Turing machine exists in two dimensions [Salo-Törmä, 2020].
    • Proof idea: Just do Schaeffer's construction in one dimension, replacing directions by speeds. A funny detail, we replace exact geometric positioning of gadgets by a counting argument showing possible positions exist.
  18. Range/radius distortion is possible in the automorphism group of full shift.
    • Asked in: [Cyr-Franks-Kra, 2016]
    • Our solution in: [Guillon-Salo, 2017]
    • Proof idea: Take any distorted reversible Turing machine (many are known) and simulate it in any way by a reversible cellular automaton (at least two ways are known).
  19. Majority network prediction is PSPACE-complete.
  20. Minimal subshifts need not have f.g. automorphism group.
  21. Chaotic reversible CA can be trace universal.
  22. Affine bipermutive CA have only affine CA in their centralizer in any dimension.
  23. The subpattern poset of a two-dimensional countable SFT can have infinite descending chains.
  24. Higher-dimensional CA are nilrigid.
  25. Cantor-Bendixson ranks of countable SFTs can be infinite
  26. There is no CA on a full shift which is transitive in the Besicovitch topology.
  27. There is a shift-invariant nonatomic measure on the full shift with the Besicovitch topology.
  28. \( \mathrm{NFA} = \mathrm{FNFA} \) in two dimensions (these are picture language classes)
  29. \( \mathrm{AFA} \subsetneq \mathrm{FAFA} \) in two dimensions (these are picture language classes)
  30. \( \mathrm{RLG} \subsetneq \mathrm{DREC} \) (these are picture language classes)
  31. The picture language classes \(\mathrm{RE}\) and \(\mathrm{REG}\) are incomparable.

1 More precisely, this is a partial (and possibly total) list of problems that were asked by someone other than me, and I am on the author list of a publically available paper/preprint where this question is solved, or (in one case) reduced to other better-known problems. In most cases I believe I was essentially involved in solving the problem, but in some cases I was somewhat useless (at least in the parts of the paper related to the specific problem) and this is clarified in a comment. Not all the solutions have been peer-reviewed (at least officially). Most of these questions were asked in a public forum in writing, a few I just heard privately. Some were not first solved by me, and if I know a previous reference I give it. In some cases our "solution" just points out a (not necessarily obvious) connection between existing results, and this has been clarified. In some cases I have also included some additional information and related open problems (but with no particular consistency). If I immediately see a one- or two-sentence summary of the proof, I give it. I have aimed for completeness rather than only included "important" results, indeed I found it best to keep evaluation of the comparative difficulty and interestingness to a minimum (whether a one sentence summary exists is not an indication of this). These are roughly in ascending order by age.


References to questions and additional info

[Rosenfeld 1978] Rosenfeld, Azriel Picture Languages (Formal models for picture recognition), Academic press, New York, 1979.

[Boyle-Lind-Rudolph, 1988] Mike Boyle, Douglas Lind, and Daniel Rudolph. The automorphism group of a shift of finite type. Transactions of the American Mathematical Society, 306(1):pp. 71–114, 1988

[Giammarresi-Restivo, 1996] D. Giammarresi and A. Restivo, Two-Dimensional Languages, in: A. Salomaa and G. Rozenberg, eds., Handbook of Formal Languages, Vol. 3 (Springer, Berlin, 1996)

[Gattaneo-Formenti-Margara-Mazoyer, 1997] G. Cattaneo, E. Formenti, L. Margara, and J. Mazoyer. A shift-invariant metric on \(S^{\mathbb{Z}}\) inducing a non-trivial topology. In Mathematical foundations of computer science 1997 (Bratislava), volume 1295 of Lecture Notes in Comput. Sci., pages 179–188. Springer, Berlin, 1997.

[Moore-Boykett, 1997] Cristopher Moore and Timothy Boykett. Commuting cellular automata. Complex Systems, 11(1):55–64, 1997.

[Manzini, 1998] G. Manzini. Characterization of sensitive linear cellular automata with respect to the counting distance. In MFCS'98, volume 1450 of LNCS, pages 825–833. Springer-Verlag, 1998.

[Lindgren-Moore-Nordahl, 1998] K. Lindgren, C. Moore and M.G. Nordahl, Complexity of Two-Dimensional Patterns, in: Journal of Statistical Physics 91, pp. 909-951, 1998

[Kari-Moore, 2001] J. Kari, C. Moore, New Results on Alternating and Non-Deterministic Two Dimensional Finite-State Automata, in: A. Ferreira, H. Reichel, eds., 18th Ann. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 2010, Springer, Berlin, 2001

[Delvenne-Kůrka-Blondel, 2006] J.-C. Delvenne, P. Kůrka, V. Blondel, Decidability and universality in symbolic dynamical systems, Fund. Inform. 74 (4) (2006) 463–490.

[Blanchard-Cervelle-Formenti, 2003] F. Blanchard, J. Cervelle, and E. Formenti. Periodicity and transitivity for cellular automata in Besicovitch topologies. In Mathematical foundations of computer science 2003, volume 2747 of Lecture Notes in Comput. Sci., pages 228–238. Springer, Berlin, 2003

[Ballier-Durand-Jeandel, 2008] Alexis Ballier, Bruno Durand, and Emmanuel Jeandel. Structural aspects of tilings. In Pascal Weil Susanne Albers, editor, Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science, pages 61–72, Bordeaux, France, February 2008. IBFI Schloss Dagstuhl.

[Guillon-Richard, 2008] Guillon, Pierre; Richard, Gaetan Nilpotency and Limit Sets of Cellular Automata. In: Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, MFCS ’08, Springer-Verlag, Berlin, Heidelberg, pp. 375–386, 2008.

[Guillon-Richard, 2010] Guillon, Pierre; Richard, Gaetan Asymptotic behavior of dynamical systems and cellular automata. arXiv preprint arXiv:1004.4743 (2010).

[Jeandel-Vanier, 2011] Emmanuel Jeandel and Pascal Vanier. \(\Pi^0_1\) sets and tilings. In Theory and Applications of Models of Computation (TAMC), volume 6648 of Lecture Notes in Computer Science, pages 230–239, 2011.

[Macauley-McCammond-Mortveit, 2011] Matthew Macauley, Jon McCammond, and Henning S. Mortveit. Dynamics groups of asynchronous cellular automata. Journal of Algebraic Combinatorics, 33(1):11–35, Feb 2011.

[Vielhaber, 2012] M. Vielhaber. Computing by Temporal Order: Asynchronous Cellular Automata. AUTOMATA & JAC 2012: 166-176.

[Hochman, 2013] Hochman, Michael Isomorphism and embedding of Borel systems on full sets. Acta Appl. Math., 126:187–201, 2013.

[Ballier-Jeandel, 2013] Alexis Ballier and Emmanuel Jeandel. Structuring multi-dimensional subshifts. ArXiv e-prints, September 2013.

[Goles-Montealegre, 2014] Eric Goles and Pedro Montealegre. Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science, 559(0):3–19, 2014.

[Schaeffer, 2014] Luke Schaeffer. A physically universal cellular automaton. Electronic Colloquium on Computational Complexity (ECCC), 21:84, 2014

[Boyle-Buzzi-McGoff, 2015] Mike Boyle, Jérôme Buzzi, and Kevin McGoff. Bowen's entropy-conjugacy conjecture is true up to finite index. Proc. Amer. Math. Soc., 143(7):2991–2997, 2015.

[Törmä, 2015] Törmä, Ilkka Structural and Computational Existence Results for Multidimensional Subshifts. PhD dissertation, University of Turku, 2015.

[Kari-Taati, 2015] Kari, Jarkko; Taati, Siamak Statistical mechanics of surjective cellular automata. Journal of Statistical Physics, 160(5):1198–1243, 2015.

[Salo-Törmä, 2015] Ville Salo and Ilkka Törmä. Category theory of symbolic dynamics. Theor. Comput. Sci., 567:21–45, 2015.

[Donoso-Durand-Maass-Petite, 2016] Sebastian Donoso, Fabien Durand, Alejandro Maass, and Samuel Petite. On automorphism groups of low complexity subshifts. Ergodic Theory and Dynamical Systems, 36(01):64–95, 2016.

[Cyr-Franks-Kra, 2016] Cyr, V., Franks, J., Kra, B.: The spacetime of a shift automorphism. ArXiv e-prints (October 2016)

[Aubrun-Barbieri-Sablik, 2017] N. Aubrun, S. Barbieri, and M. Sablik. A notion of effectiveness for subshifts on finitely generated groups. Theoretical Computer Science, 661:35–55, 2017.

[Boyle-Chuysurichay, 2018] Mike Boyle and Sompong Chuysurichay. The mapping class group of a shift of finite type. J. Mod. Dyn., 13:115–145, 2018.

[Törmä 2018] Törmä, Ilkka Cantor-Bendixson ranks of countable SFTs. arXiv preprint arXiv:1803.03605 (2018).

[Abdulla-Atig-Ciobanu-Mayr-Totzke, 2018] Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, Patrick Totzke Universal safety for timed Petri nets is PSPACE-complete. arXiv preprint arXiv:1806.08170 (2018).

[Salo, 2019c] Salo, Ville Trees are nilrigid. arXiv preprint arXiv:1905.06093 (2019).

[Hochman, 2019] Michael Hochman. Every Borel automorphism without finite invariant measures admits a twoset generator. J. Eur. Math. Soc. (JEMS), 21(1):271–317, 2019.

[van der Zypen-Cunningham, 2019] Dominik van der Zypen / Oscar Cunningham Decision problems for which it is unknown whether they are decidable – MathOverflow. https://mathoverflow.net/q/345388. Accessed: 2019-11-15.

[Ciobanu, 2019] Ciobanu, Radu. "Verification problems for timed and probabilistic extensions of Petri Nets." (2019).

[Salo-Törmä, 2020a] Salo, Ville; Törmä, Ilkka Nilpotent endomorphisms of expansive group actions. International Journal of Algebra and Computation, 2020, doi.org/10.1142/S021819672150020X.

[Castillo-Ramirez-Gadouleau, 2020] Castillo-Ramirez, Alonso; Gadouleau, Maximilien Elementary, finite and linear vN-regular cellular automata. Inform. and Comput. 274 (2020), 104533, 12 pp.

[Jalonen-Kari, 2020] Joonatan Jalonen and Jarkko Kari. On the conjugacy problem of cellular automata. Information and Computation, 274:104531, 2020. AUTOMATA 2017.

[Franks-Kra, 2020] Franks, John; Kra, Bryna Polygonal Z2-subshifts. Proc. Lond. Math. Soc. (3) 121 (2020), no. 2, 252–286.

[Epperlein-Meyerovitch, 2020] Jeremias Epperlein and Tom Meyerovitch. Iterated Minkowski sums, horoballs and north-south dynamics. arXiv e-prints, page arXiv:2009.09221, September 2020.

[Almanza-Leucci-Panconesi, 2020] Almanza, Matteo; Leucci, Stefano; Panconesi, Alessandro Tracks from hell—When finding a proof may be easier than checking it. Theoretical Computer Science 839 (2020): 21-29.

[Belk-Bleak-Matucci, 2020] James Belk, Collin Bleak, and Francesco Matucci. Embedding right-angled Artin groups into BrinThompson groups. Math. Proc. Cambridge Philos. Soc., 169(2):225–229, 2020


References to the solutions

[My master's thesis] My master's thesis, Classes of Picture Languages Defined by Tiling Systems, Automata and Closure Properties, 2011.

[Kari-Salo, 2011] Kari, Jarkko; Salo, Ville A survey on picture-walking automata. Algebraic foundations in computer science, 183–213, Lecture Notes in Comput. Sci., 7020, Springer, Heidelberg, 2011.

[Salo-Törmä, 2012] Salo, Ville; Törmä, Ilkka Geometry and dynamics of the Besicovitch and Weyl spaces. Developments in language theory, 465–470, Lecture Notes in Comput. Sci., 7410, Springer, Heidelberg, 2012.

[Salo-Törmä, 2012a] Salo, Ville; Törmä, Ilkka On Derivatives and Subpattern Orders of Countable Subshifts. AUTOMATA & JAC 2012: 23-36.

[Salo, 2012] Salo, Ville On Nilpotency and Asymptotic Nilpotency of Cellular Automata. AUTOMATA & JAC 2012: 86-96.

[Salo-Törmä, 2013] Salo, Ville; Törmä, Ilkka Constructions with countable subshifts of finite type. Fund. Inform. 126 (2013), no. 2-3, [On cover: nos. 3-4], 263–300.

[Salo-Törmä, 2013a] Salo, Ville; Törmä, Ilkka Commutators of bipermutive and affine cellular automata. Cellular automata and discrete complex systems, 155–170, Lecture Notes in Comput. Sci., 8155, Springer, Heidelberg, 2013.

[Kari-Salo-Törmä, 2014] Kari, Jarkko; Salo, Ville; Törmä, Ilkka Trace complexity of chaotic reversible cellular automata. Reversible computation, 54–66, Lecture Notes in Comput. Sci., 8507, Springer, Cham, 2014.

[Salo, 2017] Salo, Ville Toeplitz subshift whose automorphism group is not finitely generated. Colloq. Math. 146 (2017), no. 1, 53–76.

[Goles-Montealegre-Salo-Törmä, 2016] Goles, Eric; Montealegre, Pedro; Salo, Ville; Törmä, Ilkka PSPACE-completeness of majority automata networks. Theoret. Comput. Sci. 609 (2016), part 1, 118–128.

[Guillon-Salo, 2017] Guillon, Pierre; Salo, Ville Distortion in one-head machines and cellular automata. Cellular automata and discrete complex systems, 120–138, Lecture Notes in Comput. Sci., 10248, Springer, Cham, 2017.

[Salo-Törmä, 2017] Salo, Ville; Törmä, Ilkka A one-dimensional physically universal cellular automaton. Unveiling dynamics and complexity, 375–386, Lecture Notes in Comput. Sci., 10307, Springer, Cham, 2017.

[Hellouin de Menibus-Salo-Theyssier, 2020] Hellouin de Menibus, B.; Salo, V.; Theyssier, G. Characterizing asymptotic randomization in abelian cellular automata. Ergodic Theory Dynam. Systems 40 (2020), no. 4, 923–952.

[Salo, 2017a] Salo, Ville Decidability and universality of quasiminimal subshifts. J. Comput. System Sci. 89 (2017), 288–314.

[Salo, 2018] Salo, Ville Von Neumann regularity, split epicness and elementary cellular automata. CoRR abs/1804.03913 (2018). Accepted in AUTOMATA 2021.

[Salo, 2019] Salo, Ville Minimal subshifts with a language pivot property. CoRR abs/1901.04688 (2019).

[Salo, 2018a] Salo, Ville Universal gates with wires in a row. CoRR abs/1809.08050 (2018).

[Salo, 2019a] Salo, Ville A note on directional closing. arXiv preprint arXiv:1902.02076 (2019).

[Salo, 2019b] Salo, Ville Entropy pair realization. arXiv preprint arXiv:1904.01285 (2019).

[Salo-Törmä, 2019] Salo, Ville; Törmä, Ilkka Gardens of Eden in the Game of Life. arXiv preprint arXiv:1912.00692 (2019).

[Salo-Törmä, 2020] Salo, Ville; Törmä, Ilkka A Physically Universal Turing Machine. arXiv preprint arXiv:2003.10328 (2020).

[Salo, 2020] Salo, Ville Examples of Non-Busemann Horoballs. arXiv preprint arXiv:2010.07645 (2020).

[Salo, 2020a] Salo, Ville Conjugacy of reversible cellular automata. arXiv preprint arXiv:2011.07827 (2020).

[Bartholdi-Salo, 2020] Bartholdi, Laurent; Salo, Ville Simulations and the Lamplighter group. arXiv preprint arXiv:2010.14299 (2020).

[Salo, 2021] Salo, Ville Graph and wreath products in topological full groups of full shifts. arXiv preprint arXiv:2103.06663 (2021).

[Salo, 2021a] Salo, Ville Veelike actions and the MCG of a mixing SFT. arXiv preprint arXiv:2103.15505 (2021).

[Barbieri-Sablik-Salo, 2021] Barbieri, Sebastián; Sablik, Mathieu; Salo, Ville Groups with self-simulable zero-dimensional dynamics. arXiv preprint arXiv:2104.05141 (2021).

[Salo, 2021b] Salo, Ville Conjugacy of transitive SFTs minus periodics. arXiv preprint arXiv:2104.09860 (2021).