Computational generation and navigation

Core representation	State + affine transform + hierarchy address
Preferred geometry	Exact or symbolic
Navigation	Recursive or finite-state
Validation	Topology and geometry, independently

Five different computational problems

Generation produces one legal substitution patch. Recognition recovers parent supertiles from children. Local validation checks contacts and labels. Extension asks whether a finite frontier belongs to an infinite tiling, while enumeration asks for all legal patches. A hierarchy can make the first three practical without automatically solving the last two.

Undecidability results concern specified broad input classes: three connected polyhypercubes in 4D, translational monotiles in ℤ^d for d≥3, and three polycubes in a 3D translational setting.^[24]^[56]^[59] They do not make explicit Hat or Spectre substitution generation undecidable. Seven-polyomino aperiodic sets likewise illuminate the small-set frontier without changing the one-planar-monotile theorem.^[58] Separately, SAT methods can certify isohedral polyforms, but no general algorithm is known for recognizing aperiodic monotiles as an input class.^[17]

Exact coordinates and hierarchy addresses

Store every tile as a discrete state, orientation, exact or high-precision affine transform, and a stable path from the root supertile. Expand the hierarchy before clipping. Exact symbolic coordinates prevent tiny roundoff discrepancies from becoming false gaps or overlaps; floating-point coordinates remain appropriate for final rendering after topology is fixed.

Voss’s MATLAB constructor translates the S/M composition rules into coordinates and was visually checked through level eight, containing 16,908,641 Tile(1,1) instances.^[29] Tatham’s combinatorial coordinate system instead rewrites hierarchical addresses to cross tile edges, generating a local neighborhood without materializing a giant enclosing supertile. The symbolic-spectre-tiles repository provides an MPL-2.0 exact-coordinate export path; both independent implementations still require comparison with the official rules.

Finite-state navigation and automatic refinement

Recursive neighbor lookup can become expensive or ambiguous near infinite-order boundaries. Finite-state transducers read and rewrite hierarchy-address strings directly, giving bounded-state navigation for supported substitution presentations. Tatham’s neighborhood-refinement method splits ambiguous tile states until deterministic transitions become possible, then minimizes equivalent states; on Hat and Spectre inputs it recovers known refined systems. The author does not claim a universal theorem for every substitution.

GPU rendering without losing provenance

GPU renderers should instance one canonical mesh and upload compact transforms or split algebraic components. Reusser’s WebGPU notebook separates transform components so Hat-Spectre-Turtle morphs become per-frame projections and reports roughly 17 million depth-eight instances. Deep zoom can generate supertiles on demand and replace subpixel detail with simpler instances, but extreme scales expose floating-point failure and level-of-detail seams.

Rendering speed is not geometric validation. Archive the rule table, root state, depth, coordinate convention, clipping mask, transform precision, renderer revision, and file hashes. Validate polygon closure, overlap, uncovered area, edge contacts, legal states, hierarchy counts, and handedness in a separate code path.

Tool choice and scope

Prefer the official BSD-licensed hatviz and hatvalidate repositories for Hat reference generation and proof-case replay. The MIT TileOneOne code generates the straight weakly chiral polygon; it does not add strict Spectre edge modifications. Browser studios are excellent for exploration but may permit overlaps, reflections, or freeform invalid layouts. License, geometry variant, revision, and export semantics must be checked tool by tool.