Abstract In this paper, we study a reversible process (more precisely, a groupoid/group action) resembling the classical 15-puzzle, where the legal moves are to “move the unique hole inside a translate of a shape S”. Such a process can be defined for any finite subset S of a group, and we refer to such a process as simply “solitaire”. We develop a general theory of solitaire, and then concentrate on the simplest possible example, solitaire for the plane $$\mathbb {Z}^2$$ Z 2 , and S the triangle shape (equivalently, any three-element set in general position). In this case, we give a polynomial time algorithm that puts any finite subset of the plane in normal form using solitaire moves, and show that the solitaire orbit of a line of consecutive ones—the line orbit—is completely characterised by the notion of a so-called fill matrix. We show that the diameter of the line orbit, as a graph with edges the solitaire moves, is cubic. We show that analogous results hold for the square shape, but indicate some shapes (still on the group $$\mathbb {Z}^2$$ Z 2 ) where this is less immediate. We then explain in detail the connection of the solitaire to TEP and more generally permutive subshifts. Namely, the solitaire is a closure property of various sets of subsets of the group that can be associated to such a subshift, such as the independence, spanning and filling sets.

Conway's Game of Life is a two-dimensional cellular automaton . As a dynamical system , it is well-known to be computationally universal, i.e. capable of simulating an arbitrary Turing machine . We show that in a sense taking a single backwards step of the Game of Life is a computationally universal process, by constructing patterns whose preimage computation encodes an arbitrary circuit-satisfaction problem, or, equivalently, any tiling problem. As a corollary, we obtain for example that the set of orphans is coNP-complete, exhibit a -periodic configuration whose preimage is nonempty but contains no periodic configurations, and prove that the existence of a preimage for a periodic point is undecidable. Our constructions were obtained by a combination of computer searches and manual design.

We apply automata theory and Karp’s minimum mean weight cycle algorithm to minimum density problems in coding theory. Using this method, we find the new upper bound 53/126 ≈ 0.4206 for the minimum density of an identifying code on the infinite hexagonal grid, down from the previous record of 3/7 ≈ 0.4286.

We construct a two-dimensional Turing machine that is physically universal in both the moving tape and moving head model. In particular, it is mixing of all finite orders in both models. We also provide a variant that is physically universal in the moving tape model, but not in the moving head model.

Abstract We show that a cellular automaton on a one-dimensional two-sided mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from previous joint work of the author and Törmä that von Neumann regularity is a decidable condition, and we decide it for all elementary CA, obtaining the optimal radii for weak generalized inverses. Two sufficient conditions for non-regularity are having a proper sofic image or having a point in the image with no preimage of the same period. We show that the non-regular ECA 9 and 28 cannot be proven non-regular using these methods. We also show that a random cellular automaton is non-regular with high probability.

We settle two long-standing open problems about Conway's Life, a two-dimensional cellular automaton. We solve the Generalized grandfather problem: for all $n \geq 0$, there exists a configuration that has an $n$th predecessor but not an $(n+1)$st one. We also solve (one interpretation of) the Unique father problem: there exists a finite stable configuration that contains a finite subpattern that has no predecessor patterns except itself. In particular this gives the first example of an unsynthetizable still life. The new key concept is that of a spatiotemporally periodic configuration (agar) which has a unique chain of preimages; we show that this property is semidecidable, and find examples of such agars using a SAT solver. Our results about the topological dynamics of Game of Life are as follows: it never reaches its limit set; its dynamics on its limit set is chain-wandering, in particular it is not topologically transitive and does not have dense periodic points; and the spatial dynamics of its limit set is non-sofic, and does not admit a sublinear gluing radius in the cardinal directions (in particular it is not block-gluing). Our computability results are that Game of Life's reachability problem, as well as the language of its limit set, are PSPACE-hard.

To each one-dimensional subshift X, we may associate a winning shift W(X) which arises from a combinatorial game played on the language of X. Previously it has been studied what properties of X does W(X) inherit. For example, X and W(X) have the same factor complexity and if X is a sofic subshift, then W(X) is also sofic. In this paper, we develop a notion of automaticity for W(X), that is, we propose what it means that a vector representation of W(X) is accepted by a finite automaton. Let S be an abstract numeration system such that addition with respect to S is a rational relation. Let X be a subshift generated by an S-automatic word. We prove that as long as there is a bound on the number of nonzero symbols in configurations of W(X) (which follows from X having sublinear factor complexity), then W(X) is accepted by a finite automaton, which can be effectively constructed from the description of X. We provide an explicit automaton when X is generated by certain automatic words such as the Thue-Morse word.

We define a class of subshifts defined by a family of allowed patterns of the same shape where, for any contents of the shape minus a corner, the number of ways to fill in the corner is the same. For such a subshift, a locally legal pattern of convex shape is globally legal, and there is a measure that samples uniformly on convex sets. We show by example that these subshifts need not admit a group structure by shift-commuting continuous operations. Our approach to convexity is axiomatic, and only requires an abstract convex geometry that is “midpointed with respect to the shape”. We construct such convex geometries on several groups, in particular strongly polycyclic groups and free groups. We also show some other methods for sampling finite patterns, and show a link to conjectures of Gottshalk and Kaplansky.

We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the setting is equivalent to bootstrap percolation. We explore the extent to which monotonicity constrains the possible asymptotic dynamics by proving two results that do not hold in the subclass of monotone automata. First, it is undecidable whether the automaton almost surely fills the space when initialized on a Bernoulli random configuration with density p, for some/all 0<p<1. Second, there exists an automaton whose space-filling property depends on p in a non-monotone way.

Abstract We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.

We study the class of word-building games, where two players pick letters from a finite alphabet to construct a finite or infinite word. The outcome is determined by whether the resulting word lies in a prescribed set (a win for player A) or not (a w

We present constructions of countable two-dimensional subshifts of finite type (SFTs) with interesting properties. Our main focus is on properties of the topological derivatives and subpattern posets of these objects. We present a countable SFT whose