Pimp my fixpoint: sofic realization of multidimensional substitution-based shift spaces

1. Introduction

• Sofic shifts inherit an O(n^(d−1)) information bound from the thick borders of finite-type patterns, limiting what their covers can encode about large interiors.The introduction notes that known proofs of non-soficity in dimensions d ≥ 2 quantify information in patterns.Source: §1 · p. 1
• The fixed-point construction uses macro-tiles to simulate an infinite hierarchy, and prior applications establish soficity for several complex shift families.The cited examples include substitutive shifts, seas of squares, and effective shifts of low density.Source: §1 · p. 2
• Sublinear alphabet sizes, under computability conditions, give a positive soficity criterion for S-adic shifts generated by substitution sequences.The paper frames this as a generalization of the fixed-point theorem covering its previous applications.Source: §1 · p. 3
• The paper recasts fixed-point simulations as substitutions and S-adic limit spaces, using non-deterministic substitutions that may produce several rectangular patterns per symbol.This viewpoint connects hierarchical simulation with abstract multi-level tiling properties.Source: §1 · p. 3
• Lemma 3.1 allows non-monotone macro-tile sizes, rectangular tiles, and computability conditions measured across cumulative substitution sizes rather than one level.Computations may be placed in deeper layers when a current layer lacks space.Source: §1 · p. 3

§ Outline of the paper

• Processor arrays provide the parallel computation model, processing inputs of size O(N^(d−1)) in time O(N); the paper then outlines background, results, applications, proof tools, and future work.The authors describe this as the first use of processor arrays in multidimensional symbolic dynamics.Source: §1 · p. 4, § Outline of the paper · p. 4

Rectangles.

• Rectangles are represented by translated interval products, with volume, longest-edge time, and smallest-facet space measures; grids extend these measures to partitions of Z^d.For a rectangle r, time is its longest edge length and space is its volume divided by that length.Source: Rectangles · p. 4, Grids · p. 5

Boustrophedon order.

• Boustrophedon order alternates the ordering of adjacent subarrays and preserves locality, so consecutive array positions correspond to adjacent sites.The paper illustrates this order on two- and three-dimensional arrays.Source: Boustrophedon order · p. 5, Figure 3 · p. 5

Grids.

• Composing grids yields coarser partitions, and successive compositions form nested grids.The composition of two grids is a subgrid of the finer grid.Source: Grids · p. 5

Computability.

• Computability preliminaries distinguish computable, computably enumerable, and co-enumerable sets, and define effectively closed shifts through enumerable forbidden prefixes or non-halting inputs.An effectively closed set consists of infinite inputs on which a machine never halts.Source: Computability · pp. 5–6

§ 2.2. The RAM model; Word-RAM.

• The RAM model measures algorithmic operations directly, while word-RAM bounds variable and memory-cell word lengths, with O(log s) defining a log-RAM program.The model permits classical arithmetic and conditional branching in constant time; the word-length bound constrains these operations’ operands.Source: § 2.2. The RAM model · p. 6, Word-RAM · p. 7

§ 2.3. Symbolic dynamics; Shift spaces.

• Patterns are colorings of subsets of Z^d, and a shift space is a closed, translation-invariant set of configurations equivalently specified by forbidden finite patterns.Pattern occurrence allows translation, so the location of a finite pattern within a larger pattern need not be fixed.Source: Shift spaces · p. 7

Factor maps; Classes of shift spaces.

• Shift morphisms are continuous, translation-equivariant local maps; surjective morphisms are factor maps, and the paper defines SFT, sofic, and effective shifts by their forbidden-pattern presentations.A sofic shift is a factor of an SFT, and can equivalently be obtained by symbol-by-symbol projection of a nearest-neighbor SFT.Source: Factor maps · p. 8, Classes of shift spaces · p. 8

Wang tiles.

• Finite Wang tilesets define nearest-neighbor SFTs, and projecting decorated tiles to their labels yields configurations of sofic shifts.Conversely, any SFT is essentially equivalent to tilings by a finite Wang tileset.Source: Wang tiles · p. 8

Substitutions and ndill maps.

• Substitutions map symbols to rectangular patterns, while ndill maps let images depend on a finite neighborhood; both may be non-deterministic, non-uniform, and not total.Substitutions are exactly the radius-0 ndill maps; the paper focuses mainly on expanding ndill maps, whose image rectangles have side lengths at least two.Source: Substitutions and ndill maps · p. 9

§ 2.4. Substitutions, ndill maps and limit spaces

• S-adic and N-adic limit spaces arise from infinite sequences of substitutions or ndill maps, respectively, with N-adic spaces allowing varying finite alphabets and directive sets.For finite alphabets and substitutions with finite image, the associated limit shift is sofic in dimensions d ≥ 2.Source: S-adic and N-adic spaces · pp. 9–10

Alternative limit spaces.

• The article proves soficity for the infinitely desubstitutable limit space, while soficity of the alternative space defined by subpatterns of iterated images may require Property A.The alternative space is usually harder to show sofic; the authors state that respecting Property A suffices in later Theorems 3.2 and 3.3.Source: Alternative limit spaces · p. 10
• Ndill maps can encode intermediate SFT validity by returning no image for locally invalid source patterns, so their limit configurations enforce both substitution steps and finite-type constraints.The resulting limits correspond to substitution sequences whose intermediate configurations are valid in their respective SFTs; radius-1 ndill maps allow substitutions of valid Wang tilings.Source: Ndill maps and SFTs · pp. 10–11

Parallelism and computability.

• Any N-adic limit space generated by arbitrary ndill maps can also be realized by parallel ndill maps on larger alternative alphabets, with alphabet blowup depending on preceding map image sizes.Parallel maps distribute image computation across individual output cells; deterministic computable ndill maps are parallel, but not all ndill maps are.Source: Parallelism and computability · p. 11

§ 2.5. Recognizability and simulation

• Recognizability requires at most one source configuration and grid for each image, while simulation explicitly encodes a grid and preimage information to recover the simulated shift.The inverse of a simulation is recognizable over the full shift, though it need not be deterministic.Source: § 2.5. Recognizability and simulation · p. 12

§ 3.1. Main fixed-point lemma

• Lemma 3.1 gives a positive soficity criterion for a Wang-tiling limit space when its grid growth and substitution computation satisfy the stated bounds and its base tiling projects to a sofic shift.The criterion assumes a log-RAM program for a parallel expanding substitution, a sequence of valid tilings linked by the substitutions, and bounds on color lengths and computation times.Source: § 3.1. Main fixed-point lemma · p. 13

3.2.1. Effectivity.

• Given the substitution program and constants, the proof effectively constructs a finite-type cover, and preimages of limit-space configurations in that cover are computable.The cover itself can be represented as an S-adic limit space with a recognizable decomposition that continuously recovers each level configuration from the cover configuration, grids, and projected level configuration.Source: §3.2.1 · p. 13, §3.2.2 · p. 14

3.2.3. Entropy.

• If the substitution is recognizable and its program is unambiguous, the finite-type cover has the same entropy as the limit space.The construction’s patterns comprise the projected pattern, S-adic levels, and associated computations; under the stated assumptions it introduces no artificial entropy.Source: §3.2.3 · p. 14

3.2.4. Ndill maps.

• The criterion extends to computable ndill maps when their substitution radius grows as O(μ̃_ℓ^β) with α + d·β < 1, or when non-parallel image growth satisfies the analogous bound.For non-parallel maps, the grid sizes must grow as O(μ̃_ℓ^β′) with α + d·β′ < 1.Source: §3.2.4 · p. 14, §3.2.5 · p. 14

§ 3.3. Applications of the fixed-point lemma to N-adic limit spaces

• Theorems 3.2 and 3.3 establish soficity for N-adic limit spaces generated by computable sequences of expanding maps on fixed-size squares or by effectively closed directive sequences of bounded-size maps.Theorem 3.2 assumes parallel maps, sublinear alphabet growth, and polylogarithmic radii; the section notes it also applies to non-parallel maps with constant or polylogarithmic grid growth, while Theorem 3.3 drops the parallel requirement.Source: § 3.3. Applications of the fixed-point… · pp. 14–15

Relation to existing literature.

• The authors present Lemma 3.1 as the first explicit abstraction of the fixed-point construction in substitution terms, including limit spaces with substitution alphabets of increasing, unbounded cardinality.The construction quantifies information through the sizes of successive alphabets, which bound what each map can process in its hierarchical verification of limit-space patterns.Source: Relation to existing literature · p. 16, Soficity · p. 17

Numeric bounds.

• The lemma’s parameter bounds are partly proof artifacts: the size bound can exclude arbitrarily small rectangles, while a computation bound arises from synchronizing information across levels.The section says a more natural condition δ < 1 is possible, but would not allow grids with μ(g_ℓ) = 2.Source: Numeric bounds · p. 16

Differences between Theorems 3.2 and 3.3 and Lemma 3.1.

• Theorems 3.2 and 3.3 restrict Lemma 3.1’s non-uniform grids, but together establish soficity for shifts with information flow O(n^α) where α < d − 1.Lemma 3.1 permits a wider range of grid sizes and corresponding computational capacities at each level.Source: Differences between Theorems 3.2 and… · p. 16, Soficity · p. 17

Soficity

• The example’s ndill maps guess a configuration at level 1, validate it and apply the factor map at level 0, and map blanks to blank patterns at higher levels, meeting Theorem 3.2’s conditions.At levels ℓ≥2 the alphabets are singletons and the associated maps are computable in constant time.Source: Soficity · p. 17
• Checking neighboring macro-tiles locally at each level restricts fault-line overlaps to patterns locally interpretable as deriving from a common ancestor, yielding a limit space with the same grids and alphabet and a comparable neighborhood.The realization can require increasing the neighborhood to a generating set of Zd if it does not already contain one.Source: Soficity · p. 17
• In natural cases, particularly with a stationary directive sequence, Theorems 3.2 and 3.3 still apply when checking new local constraints requires only a constant number of additional substitutions.The added checks may otherwise become too computationally intensive for the fixed-point lemma.Source: Soficity · p. 17

§ 4.1. S-adic shift spaces

• For any finite set of expanding multidimensional substitutions and any effectively closed set of directive sequences over it, the resulting S-adic limit space is sofic.This recovers [AS14, Theorem 5]; the single-substitution case also recovers the soficity result of.Source: § 4.1. S-adic shift spaces · p. 18

§ 4.2. Embedding computably enumerable information

• Every effectively closed set of binary infinite words has a sofic two-dimensional shift in the same Medvedev degree.The associated finite-type cover is also in that degree, recovering; the equivalence also recovers and proves undecidability of SFT emptiness via.Source: § 4.2. Embedding computably enumerable… · pp. 18–19

Toeplitz shifts.

• Every effective Toeplitz shift is sofic.A rectangular Toeplitz shift is an S-adic space directed by Toeplitz substitutions, each with a coincidence; for the binary examples, configurations other than the two constant ones permit computable recovery of the substitution grid and source configuration.Source: Toeplitz shifts · p. 19

Entropies.

• For every right-computable real γ ≥ 0, there is a binary two-dimensional shift of finite type with entropy γ.The construction turns symbol frequencies into entropy using a nondeterministic substitution, and yields a finite-type cover with equal entropy.Source: Entropies · p. 21

Entropy dimensions.

• Every Π0_3-computable (resp. Σ0_2-computable) γ in [0, 2] is the upper (resp. lower) entropy dimension of a sofic binary two-dimensional shift.In dimension d, the construction realizes any γ in [0, d] under the same assumptions.Source: Entropy dimensions · p. 22

§ 4.4. Intrinsic universality

• For every d ≥ 2, an SFT can simulate every member of any computably enumerable family of non-empty sofic shifts in dimension d.The S-adic structure of the fixed-point construction is locally recognizable; the result rephrases [LW10, Theorem 5.2] and is related to a deterministic version in [Zin15, Theorem 48].Source: § 4.4. Intrinsic universality · p. 22
• A sofic cover can simulate every member of any computably enumerable family of nonempty sofic shifts, but no sofic shift simulates all nonempty sofic shifts [Bal13].The construction embeds each finite-type cover at a corresponding level of the hierarchy, yielding a sofic limit space.Source: § 4.4. Intrinsic universality · p. 22

§ 4.5. Effective subdynamics and periodic lifts

• A Zd shift is effective if and only if its periodic lift is a sofic Zd+1 shift.The construction distributes checks of O(n) bits across chunks of O(log n), and performs pattern checks within local constraints of the ndill map rather than using robots to visit neighboring macro-tiles.Source: § 4.5. Effective subdynamics and… · pp. 23–25

§ 4.6. Shifts defined by information quantification

• Sufficient soficity criteria must account for both useful pattern information and the time needed to compute efficient descriptions; the low-density result generalizes [Des21, Theorem 5] from Z2 to arbitrary Zd for d ≥2.The paper presents this as a computability-aware approach to information-based soficity conditions.Source: § 4.6. Shifts defined by information… · p. 25, §4.6.1 · p. 25

4.6.1. Low-density shifts.

• For α < d − 1, every effective shift over the binary alphabet whose patterns on J_n^d contain fewer than O(n^α) black cells is sofic.Source: §4.6.1 · p. 25

4.6.2. Gap shifts.

• In dimension d ≥2, a gap shift XG,f is sofic if and only if its increasing gap function f is upper semi-computable.The construction encodes distance bounds in tiles and checks the distance condition at the hierarchy level responsible for that bound.Source: §4.6.2 · p. 26

4.6.3. Seas of squares.

• For computably co-enumerable S, the shift whose black connected components are squares of sizes in S is sofic.The squares may have any sizes in S, and their components are independent.Source: §4.6.3 · p. 27
• Starting from the full square shift, substitutions track square sizes and large rectangles, distribute size records to smaller tiles, and nondeterministically introduce new rectangles.The resulting limit space is the S-square shift.Source: §4.6.3 · pp. 28–29
• Restricting each size list to O(L_ℓ^(2/3)) entries makes the substitution maps computable in O(L_ℓ^(2/3) · poly(ℓ)) time, yielding soficity by Theorem 3.2.The bound follows because the sum of squares of distinct sizes fitting in an n × n window is at most n^2.Source: §4.6.3 · p. 29

§ 5.1. Classical results from computability

• Computability tools provide a universal interpreter, a hardcoding transformation, and fixed-point programs that preserve a total computable transformation’s behavior with controlled time and word length.The interpreter runs in O(Te(I)) time with word length We(I) + O(log |e|); the fixed-point program has time O(TF(e)(I)) + O(1) and word length WF(e)(I) + O(1).Source: § 5.1. Classical results from… · pp. 29–30

5.2.1. Processor arrays.

• Processor arrays place identical register-machine processors on a rectangle, synchronously execute instructions, and use neighbor communication to define a nondeterministic partial input-output function.The model is presented as suitable for computations embedded in d-dimensional rectangular tilings.Source: §5.2.1 · p. 31, § 5.2. Grid-connected processor arrays · p. 31

5.2.2. The sorting problem.

• A deterministic processor-array program solves sorting in boustrophedon order, enabling nondeterministic processor arrays to efficiently simulate log-RAM programs.The sorting result applies to any rectangular domain.Source: §5.2.2 · p. 31, §5.2.3 · p. 32
• For logarithmic-word RAM programs and timeout t no greater than the rectangle’s volume, a processor array’s accepting outputs are exactly the program’s outputs computed within t.The simulation uses guessed computation traces and sorting to check local consistency; accepting computations keep each processor’s word length O(log volume).Source: §5.2.3 · p. 32
• Program eU sorts output-bit trace variables by boustrophedon domain addresses using Proposition 5.4, then copies stored values to outputs; failed local checks reject, otherwise computation accepts.Source: §5.2.3 · p. 33

§ 6.1. Drawing rectangles with Wang tiles

• Valid rectangle tiles draw each rectangle, and adding a blank tile makes valid configurations exactly independent rectangles on a blank background.Source: § 6.1. Drawing rectangles with Wang… · p. 34

§ 6.2. Drawing grids with Wang tiles

• Valid grid tilings and rectangular grids determine one another uniquely, with tile fields recording each rectangle’s normalized shape and position modulo the grid.Source: § 6.2. Drawing grids with Wang tiles · p. 34

§ 6.3. Drawing wires with Wang tiles

• The routing lemma realizes equal-sized boundary source and receiver patterns, with wires of length O(Σn_k).Wires are contiguous paths pairing colored starts and ends.Source: § 6.3. Drawing wires with Wang tiles · p. 35

§ 7.0. Overview of the fixed-point construction

• The fixed-point construction organizes tilesets into a hierarchy in which each level deterministically block-simulates the next.Source: § 7.0. Overview of the fixed-point… · p. 37, §7.0.1 · p. 37

7.0.1. The classical construction.

• Square macro-tiles emulate Wang tiles: border bits form macro-colors, adjacent tiles match them, and embedded computations determine the next tileset.The zoom must allow enough time for computation; the fixed-point theorem resolves the dependency on the next tileset’s program.Source: §7.0.1 · p. 37
• For non-uniform d-dimensional rectangles, uniform bounds on smallest facets and largest edges support processor-array simulations, while the routing lemma transmits information within macro-tiles.The processor array uses the geometry’s parallelism to operate in O(n) time on objects of size O(n^(d−1)).Source: §7.0.2 · p. 37
• A level computes several substitution steps together, grouping them until the product of grid-size bounds is large enough for a simulation step despite arbitrarily small rectangles.The construction uses κ to partition substitution steps into segments, then interleaves their computations with simulation steps to keep the resulting macro-tiles simulable.Source: §7.0.3 · p. 38

§ 7.1. Deciding the hierarchy of substitutions and simulations

• The staircase lemma establishes interleavings ι and κ for sufficiently large Ks, coordinating blocks of substitution steps with successive fixed-point simulations.Each level ι(n) computes the substitutions in its κ-block and must still be able to simulate the next designated level.Source: § 7.1. Deciding the hierarchy of… · pp. 38–39, §7.0.4 · p. 38

§ 7.2. The algorithm F (e)

• The algorithm F(e) transforms a RAM program into a log-RAM program defining a nondeterministic function whose accepted Wang tiles and colors encode the construction’s constraints.It progressively enumerates restrictions on color tuples, defining the tileset by checking whether those constraints hold.Source: § 7.2. The algorithm F (e) · pp. 40–41

Housekeeping.

• A technical omission in the informal description is that the next configuration and grid may not fit in the current tiles’ storage bounds, so the next simulation level defines them with synchronization.The note attributes this limitation to the numerical bounds supplied by the staircase lemma.Source: Housekeeping · p. 41

§ 7.3. Hierarchical positioning

• Given the existing bounds and level, the tileset chooses κ′, fixes bounds for new grids, embeds further substitution steps, and selects a level ι′ for the next simulation.The sequence of input bounds determines κ via its length.Source: § 7.3. Hierarchical positioning · p. 42, Uniform bounds · p. 42

Uniform bounds.

• Staircase-lemma conditions persist when the parameter segment is extended, ensuring consistent parameters and uniform bounds across tiles in valid configurations.The same bound data is copied into each tile’s decoration.Source: Uniform bounds · p. 42

Grids and positions.

• Position fields in any valid Sι-tiling uniquely determine a finite sequence of nested grids.They determine grids gℓ and product grids ˜gℓ; the fields locate tiles in the former but do not reveal exact positions or rectangle sizes in the latter.Source: Grids and positions · p. 43
• The final grid gκ′−1 is represented implicitly by neighboring sets because the color word length may be too small to store its rectangles and positions.These sets are synchronized with the neighbor field at the next level of fixed-point simulation.Source: Neighbors · p. 44

Neighbors.

• Neighbor fields encode whether adjacent rectangles belong to the same parent rectangle, remain constant within rectangles, and synchronize the final-level grid at the next simulation level.For levels below the final one, position fields determine the neighbor entries; final-level entries are synchronized at the next level.Source: Neighbors · p. 44

§ 7.4. Macro-tiles

• A level-ℓ macro-tile is a rectangular pattern whose tiles form one complete rectangle at level ℓ−1, and it uniquely determines its nested lower-level macro-tiles.Each macro-tile is a union of level-(ℓ−1) macro-tiles.Source: § 7.4. Macro-tiles · p. 44

§ 7.5. σ-macro-tiles (of level ι′)

• A tiling of Sι supplies grids at intermediate levels, one of which is designated ι′ for the next fixed-point simulation.Source: § 7.5. σ-macro-tiles (of level ι′) · p. 45

Level of simulation.

• The p-level field is constant across valid Sι-tilings, and any level in {κ, …, κ′ −1} may be chosen where the bound field determines κ and κ′.Source: Level of simulation · p. 45

Macro-tiles.

• A σ-macro-tile is a macro-tile whose level matches its p-level field; the choice’s correctness is checked at the next simulation level.Source: Macro-tiles · p. 45

7.5.1. Computation zone.

• Each computation zone is the cut Cut_N(r), with N = μ̃ι′/μ̃ι, and its compzone fields identify exactly the positions within that cut.The cut contains the origin, may not span the full macro-tile domain, and positions fit in O(log μ̃ι′) bits.Source: §7.5.1 · p. 46

Embedding computations.

• The computation zone embeds a processor-array space-time diagram, with layer n recording the array after 2Ksim · n computation steps.The processor program terminates within Ksim · max₁≤k≤d−1 nk steps, and each tile embeds 2Ksim steps to provide sufficient time.Source: Embedding computations · pp. 47–48

Folding the arguments of the computation.

• An arg field constrains input and output bits on adjacent tiles to follow their respective boustrophedon indexing.Source: Folding the arguments of the computation · p. 48
• Input variables on a computation zone’s input facet form the folded pattern of an input array, with a similar folding claim for output variables.Processor fields use O(Kw · log∥c̃∥) bits and argument fields use log∥c̃∥ bits.Source: Folding the arguments of the computation · p. 49

7.5.2. Macro-colors.

• A σ-macro-tile’s outward-facing border bits form binary macro-colors that match across adjacent facets, so the induced configuration is a valid Wang tiling.For each level-ι′ product-grid position, the macro-colors describe a tile in T∗ with blank decoration.Source: §7.5.2 · pp. 49–50

7.5.3. Wirings.

• Wires route macro-color bits from the macro-tile’s borders to its computation zone, placing each facet’s color in the corresponding input argument; the decoration argument is not wired.The decoration is instead read computationally from I[2d+4].Source: §7.5.3 · p. 52

7.5.4. Communication with the next level of the simulation.

• A color field constant across the tiles of a σ-macro-tile can initialize an input argument on its computation zone.This establishes the communication mechanism used to pass information to the next simulation level.Source: The copying method · p. 52

The copying method.

• The copying method makes tiles on the computation zone’s input facet enforce that a tile’s foo field matches the corresponding bits of an input argument.The match is checked when the field’s argument index equals the input variable’s index.Source: The copying method · p. 52

Initializing the input facet.

• The input facet initializes I[0]–I[3] by copying the global parameters, level, bound data, and higher-level position data, respectively.These values are copied from the global function, decoration fields, and position field as specified for each argument.Source: Initializing the input facet · p. 52

Reading the output facet.

• The output-reading method copies O[0], a set of directions, into the neighbor field; O[1]–O[3] are reserved for later computations.The copied directions are recorded in the eponymous neighbor-field entry.Source: Reading the output facet · p. 52

§ 7.6. τ-macro-tiles (of level κ ≤ℓ< κ′)

• Each level κ≤ℓ<κ′ adds τ-compzone, τ-processor, and τ-arg fields to embed a parallel computation of the substitution τ.The processor uses the log-RAM program ⟨τ⟩; computation zones have bounds N=Qℓ−1.Source: §7.6.1 · p. 53, § 7.6. τ-macro-tiles (of level κ ≤ℓ< κ′) · p. 53
• τ-compzone and τ-processor fields use Kw·O(log μ̃ℓ) bits individually, with collective length polylog(Ks)·Kw·O(μ̃^{2δι}) across levels κ≤ℓ<κ′.τ-wire fields at level ℓ have O(log μ̃ℓ) bits.Source: §7.6.1 · p. 53, §7.6.2 · p. 54
• τ-color fields define Wang tilings, while τ-wire fields route macro-color bits through computation zones to the substitution output facet.Outside computation zones, wires carry bits along straight lines; inside, the routing lemma carries them to the input facet.Source: §7.6.2 · p. 54, §7.6.3 · p. 54
• τ-consistency fields connect neighboring macro-tiles in the same next-level grid so their parallel computations use the same Wang tile.They carry bits between computation zones and use the routing lemma to link zone borders to input facets.Source: §7.6.3 · pp. 54–55
• The τ-processor computes each substitution step from rectangle, position, and tile arguments, with input and output arrays folded along Boustrophedon-indexed facets.The arguments are initialized on the input facet, and successive levels synchronize an output facet with nested sub-tile input facets.Source: §7.6.1 · p. 53, §7.6.4 · p. 55, Substitution shapes · p. 55
• A unique nested τ-macro-tile containing the corner has a facet inside the larger tile’s input facet, enabling cross-level routing called a “pipe.”This supplies a route between nested levels and supports the superimposed hierarchy of substitution steps.Source: § 7.6. τ-macro-tiles (of level κ ≤ℓ< κ′) · p. 53, §7.6.4 · p. 55

Substitution shapes.

• When ℓ < κ′−1, the two position arguments can be initialized directly on the input facet from the position field.Source: Substitution shapes · p. 55
• For every τ-macro-tile below level κ′−1, its input array records its position field as I[0] = rℓ and I[1] = iℓ.Source: Substitution shapes · p. 55
• At level κ′−1, two routing stages carry position data from a σ-macro-tile’s output to the corresponding input arguments of the containing τ-macro-tile.The first stage routes to a shared facet; the second rearranges the bits into their input-array positions.Source: Substitution shapes · p. 55
• The τ-pos-pipe fields use W1 and W2 to route entries from the computation-zone output, across a shared facet, and into their corresponding input-array positions.The entries carry a coordinate and a bit; W1 handles the first route and W2 the second.Source: Substitution shapes · pp. 55–56
• At level κ′−1, the input arguments I[0] and I[1] equal the output arguments r and i of the σ-macro-tile covering the corner 0.Source: Substitution shapes · p. 56

• Claim 11 shows that output arguments O[0], …, O[2d] of a level-(ℓ+1) macro-tile copy input arguments I[3], …, I[2d+3] from a level-ℓ tile.The shared input symbol among the level-ℓ tiles forming the higher-level macro-tile makes synchronization through its corner tile sufficient.Source: Substitution symbols · p. 57
• Claim 12 establishes that every pixel position in a macro-tile’s domain has its rectangle and position recorded in the corresponding pixel position field.This holds at levels κ−1, κ, and κ′−1.Source: Substitution symbols · p. 57
• For input synchronization, σ-macro-tiles encode (i, j, b) in output argument O[3]; τ-in pipe fields carry tuples from those touching the smallest facet and route them to input bit I[i + 2][j] = b.Source: Substitution symbols · pp. 57–58
• Claim 13 ensures each nonblank σ-macro-tile output (i, j, b) lies along the smallest facet and carries the matching symbol bit b = a_i(j).This placement makes the τ-in pipe wire starts satisfy the routing lemma’s hypotheses, so a wiring is possible.Source: Substitution symbols · p. 58
• For output synchronization, three successive τ-out pipe routings carry output bits to the smallest facet, permute them across level-(κ−1) macro-tiles, then route them within those tiles.Because corresponding smallest facets across simulation levels may differ, the destination facet is nondeterministically guessed in each level-(κ−1) macro-tile.Source: Substitution symbols · p. 59

Substitution symbols.

• For every output position (i, j), exactly one Wang tile in the level-κ τ-macro-tile carries the corresponding third τ-out pipe end entry.The output symbol aκ is taken from the computation zone’s output arguments.Source: Substitution symbols · p. 61
• The bit recorded by that unique tile is the output symbol’s bit ai(j).Source: Substitution symbols · p. 61
• The tile lies on the facet selected by its out-destination field in its containing level-(κ−1) macro-tile.Alternative sub-macro-tile out-destination choices can be accommodated, up to rewiring the third τ-out pipes.Source: Substitution symbols · p. 61

§ 7.7. Finalizing the algorithm F (e)

• F(e) is designed to recognize the tileset Sι for fixed arguments Ks, Kw, ι, (µℓ, λℓ), and (rℓ, iℓ).Source: §7.7.1 · p. 61
• The algorithm accepts a tile when it satisfies the conditions specified in the preceding proof sections.Source: §7.7.1 · p. 61
• The final construction makes F(e) the recognizer for the tileset defined by those conditions.Source: §7.7.1 · p. 61

7.7.1. Exit and return.

• A valid computation of φF(e) accepts a tile exactly when it satisfies the previously specified conditions, returning (Nκ−1, rκ−1, iκ−1, u).Source: §7.7.1 · p. 61
• The returned tuple includes the neighbor field Nκ−1 and the tile’s level-κ−1 position entries rκ−1 and iκ−1.Source: §7.7.1 · p. 61
• The output exposes neighbor, position, and τ-out-pipe data on lower-level output facets for the previous simulation level to read and route.Source: §7.7.1 · p. 61

7.7.2. Time complexity and word length.

• Validity checks use additions, multiplications, copies, and comparisons on large integers and binary strings, implemented in quasi-linear time in the log-RAM model.The input sizes are given as |I| + Kw · |I[3]| + |e|.Source: §7.7.2 · p. 61

§ 7.8. Fixed point theorem

• The computable total transformation F maps a program e to a program defining the Wang tile sets, and a fixed-point program makes all simulation levels use the same behavior.The construction uses e to determine the program implemented in the next level’s processor fields.Source: § 7.8. Fixed point theorem · p. 62, §7.8.1 · p. 62

7.8.1. Fixed point theorem.

• The fixed-point program e satisfies φe = φF(e), Te(I) = O(TF(e)(I)) + O(1), and We(I) = WF(e)(I) + O(1), and is itself log-RAM.The time and word-length bounds are inherited from F(e) up to the stated additive constants.Source: §7.8.1 · p. 62

7.8.2. Fixing constants.

• Choosing Kw = √Ks and Ks sufficiently large makes the computation-zone and word-length bounds hold for every ˜µℓ when 2δ < γ.The fixed constants provide enough embedded computation for the required simulations.Source: §7.8.2 · p. 62

§ 7.9. End of the proof

• Configurations of X encode nested grids, substitution tiles, and adjacency constraints, while a uniform bound on grid cells makes X a shift of finite type.The alphabet is finite because the construction bounds κ′ by a fixed N.Source: The shift X · p. 63
• The constructed shift X projects onto exactly ←− X⟨τ⟩, so the substitution limit space is sofic.The proof establishes both inclusions between the projection and the limit space.Source: End of the proof · pp. 64–65

End of the proof.

• Compactness and a diagonal argument complete locally valid fields on expanding domains, yielding configurations whose projections belong to the limit space.The construction uses expanding substitution grids and embedded accepting computations.Source: End of the proof · p. 65

Initialization.

• The initialization uses σ-macro-tiles to produce a new tiling whose processor computations output the data defining the next grid and simulation level.The output position fields collectively define a valid grid gκ′−1.Source: Induction · p. 65

Induction.

• At each induction step, τ-macro-tile fields encode image and source tiles, accepting computations, and pipe connections that enforce consistency across substitution levels.The pipes ensure tiles in the source configuration agree with the corresponding higher-level configuration.Source: Induction · p. 66
• Induction yields configurations x(ℓ) with x(ℓ+1) mapped to gℓx(ℓ) by τ in time K · ˜µℓ^γ, and the growth conditions make x a valid limit-space configuration.The resulting configuration satisfies f(x(0)) = x.Source: Induction · p. 66

§ 7.10. Final word

• Computing several τ-steps inside one macro-tile is possible but yields significantly worse bounds on grid growth and τ’s computational requirements.The embedding limits the word length of symbols in x(ℓ+n) to O(˜µℓ^α) when computing n steps.Source: Pre-composition vs. parallel… · p. 66

Algorithmic vs. geometric computations.

• Independent tiles embed t · N^d RAM steps in segments, whereas collective processor-array simulation embeds t · N^(d−1) steps; distributing τ computations reduces output size and allows more flexibility.The collective array can perform the computation on a single non-distributed machine.Source: Algorithmic vs. geometric computations · p. 67
• Each cover configuration uniquely determines an S-adic structure for its projection, and every structure satisfying the lemma’s hypotheses can be implemented in the cover.Factor maps recognize the macro-tiles at each level.Source: Algorithmic vs. geometric computations · p. 67

Entropy of the construction.

• Embedded computations add no entropy when unambiguous; routing and τ-out-pipe choices may add patterns, but fixed layouts can avoid those wiring ambiguities.The passage relates pattern complexity to ambiguous computations and valid S-adic structures.Source: Entropy of the construction · p. 68

8. Perspectives

• The fixed-point lemma's finite-type cover needs further study, including whether it is minimal or uniquely ergodic when the original N-adic space has those properties.The authors also ask whether its projection is almost one-to-one or preserves pattern complexity up to a polynomial factor.Source: §8 · p. 68
• Preserving directions of determinism between a multidimensional shift and its cover required partial reversible cellular automata in related work [Zin16].Source: §8 · p. 68
• A huge class of sofic shifts, including N-adic shifts with injective ndill maps, has an equal-entropy cover, but whether every sofic shift does remains open.Source: §8 · p. 68
• The construction gives a sufficient condition for multidimensional soficity, but a gap remains when communication complexity between two zones is exponential in their boundary [GJ15].Source: §8 · p. 68
• Obstacles to extending the fixed-point construction beyond Zd remain unclear, although S-adic formalism exists in all countable groups and substitutive limit-set soficity has been proved in a more general graph setting.Source: §8 · p. 68