The subshift is called strongly aperiodic if this action is free: that is, if no non-trivial group element takes any configuration to itself. The map ( h, ω ) ↦ ω h is easily checked to be an action. Note that G acts on a subshift of finite type in an obvious way: if h ∈ G and ω is a configuration, then so is the function ω h defined by ω h ( g ) = ω ( h − 1 g ). Note that the set of tilings of the plane with a given set of Wang tiles is a subshift of finite type determined by the rules that stipulate when two tiles may be placed next to each other, each of which is given by a forbidden pattern of size 2. The functions ω that satisfy this condition are called configurations. The set of all functions ω such that no pattern p ∈ P occurs in ω is called the subshift of finite type determined by P. Now let P be a finite set of forbidden patterns. Given a function ω : G → A, say that the pattern p occurs in ω if there exists some g ∈ G such that ω ( g x ) = p ( x ) for every x ∈ X. Define a pattern to be a function p : X → A, where X is some finite subset of G. Let G be a group (which will be infinite) and let A be a set of symbols, which we can think of as our “tiles”. The notions of Wang tilings and aperiodicity have been fruitfully generalized from Z 2 to more general groups, as follows. (The result appeared in paper form in 1966.) Wang believed that every tiling should be periodic, but his student Robert Berger showed in his PhD thesis in 1964 that the the tiling problem could be used to encode the halting problem, thereby proving that there was no algorithm for solving the former, which yielded the first known example of a set of tiles that could tile the plane but only aperiodically. Wang observed that if every set of Wang tiles admits a periodic tiling, then there is an algorithm for deciding whether any given finite set of Wang tiles can tile the plane, since if it cannot, then by an easy compactness argument there is some finite subset of the plane that cannot be tiled, whereas if it can, then one can do a brute-force search for a fundamental domain of the tiling. (Also, tiles are not allowed to be rotated.) Each tile is a unit square with edges marked in a certain way, and two tiles can be placed next to each other if and only if the adjacent edges have the same marking. In 1961, the mathematician and philosopher Hao Wang introduced the notion that we now call a Wang tiling of Z 2. A geometric simulation theorem on direct products of finitely generated groups, Discrete Analysis 2019:9, 25 pp.

Subshift disjoint from a given subshift