"""Self-assembling tile computer (abstract tile assembly model). Computation is the growth of a crystal. The program is a finite set of square tiles; each edge carries a glue label with an integer strength. A seed is placed and tiles accrete onto the assembly by one rule: a tile binds at an empty site if the summed strength of the glues that match its already-present neighbors is at least the temperature tau. That binding rule is a threshold gate, bind = H( sum_d strength_d * match_d - tau ), a weighted sum of matching-glue indicators against tau, so every attachment is decided by the same Heaviside neuron the rest of the repository is built from. At tau = 2 the model is Turing-universal (Winfree 1998): a directed tile set grows a unique structure, and that structure is the trace of a computation. Sides are N,E,S,W; a tile's N glue abuts its north neighbor's S glue, and so on. A glue label "" is the null glue (strength 0, matches nothing). Glue strengths are a property of the label (matching glues have equal strength), held in a map. """ from __future__ import annotations from typing import Dict, List, Optional, Tuple # side -> (dx, dy, my_side, neighbor_side) _SIDES = [(0, 1, "N", "S"), (1, 0, "E", "W"), (0, -1, "S", "N"), (-1, 0, "W", "E")] class Tile: __slots__ = ("N", "E", "S", "W", "name") def __init__(self, N="", E="", S="", W="", name=""): self.N, self.E, self.S, self.W, self.name = N, E, S, W, name def glue(self, side): return getattr(self, side) def bind_strength(A: Dict[Tuple[int, int], Tile], x: int, y: int, t: Tile, strength: Dict[str, int]) -> int: """Summed strength of t's glues that match the abutting neighbor glues.""" s = 0 for dx, dy, side, opp in _SIDES: nb = A.get((x + dx, y + dy)) if nb is None: continue g = t.glue(side) if g and g == nb.glue(opp): s += strength.get(g, 1) return s def binds(A, x, y, t, tau, strength) -> bool: """The threshold-gate binding decision: H(sum strength*match - tau).""" return bind_strength(A, x, y, t, strength) >= tau def grow(tileset: List[Tile], seed: Dict[Tuple[int, int], Tile], tau: int, strength: Dict[str, int], bounds: Tuple[int, int, int, int], max_tiles: int = 100000) -> Tuple[Dict[Tuple[int, int], Tile], bool]: """Directed growth from a seed. Returns (assembly, deterministic): at every site at most one tile binds when the set is directed, so the assembly is unique. deterministic=False flags a site where two tiles could bind.""" x0, y0, x1, y1 = bounds A = dict(seed) deterministic = True changed = True while changed and len(A) < max_tiles: changed = False frontier = set() for (x, y) in list(A): for dx, dy, _, _ in _SIDES: p = (x + dx, y + dy) if p not in A and x0 <= p[0] <= x1 and y0 <= p[1] <= y1: frontier.add(p) for (x, y) in frontier: binders = [t for t in tileset if binds(A, x, y, t, tau, strength)] if len(binders) == 1: A[(x, y)] = binders[0] changed = True elif len(binders) > 1: deterministic = False return A, deterministic # --------------------------------------------------------------------------- # XOR / Sierpinski tile set: value(x,y) = value(x-1,y) XOR value(x,y-1) # --------------------------------------------------------------------------- def rule2_tileset(fn) -> List[Tile]: """Rule tiles for value(x,y) = fn(W-input, S-input): four tiles, each binds cooperatively (S and W, strength 1 each = tau) and emits fn on N and E.""" ts = [] for s in (0, 1): for w in (0, 1): v = fn(w, s) ts.append(Tile(N=f"v{v}", E=f"v{v}", S=f"v{s}", W=f"v{w}", name=f"R w{w} s{s} -> {v}")) return ts def sierpinski_tileset() -> List[Tile]: return rule2_tileset(lambda w, s: w ^ s) def _row_col_seed(bottom: List[int], left: List[int]): """Seed the bottom row (y=0) and left column (x=0) with fixed value tiles, presenting value glues north and east for the rule tiles above/right.""" seed = {} for x, b in enumerate(bottom): seed[(x, 0)] = Tile(N=f"v{b}", E="", S="", W="", name=f"seedB{x}={b}") for y, l in enumerate(left): if y == 0: continue seed[(0, y)] = Tile(N="", E=f"v{l}", S="", W="", name=f"seedL{y}={l}") return seed def _test_binding_gate(): """The binding decision is exactly the Heaviside threshold gate.""" strength = {"v0": 1, "v1": 1} ts = sierpinski_tileset() A = {(1, 0): Tile(N="v1"), (0, 1): Tile(E="v0")} bad = 0 for t in ts: for x, y in [(1, 1)]: w = sum(strength.get(t.glue(side), 1) for dx, dy, side, opp in _SIDES if A.get((x + dx, y + dy)) and t.glue(side) and t.glue(side) == A[(x + dx, y + dy)].glue(opp)) gate = 1 if (w - 2) >= 0 else 0 # H(sum*match - tau) if gate != int(binds(A, x, y, t, 2, strength)): bad += 1 print(f" binding decision == Heaviside gate H(sum-tau): {'OK' if bad == 0 else 'FAIL'}") return bad == 0 def _test_rule2(fn, name, n=24): strength = {"v0": 1, "v1": 1} bottom = [1 if x == 0 else 0 for x in range(n)] left = [1 if y == 0 else 0 for y in range(n)] seed = _row_col_seed(bottom, left) A, det = grow(rule2_tileset(fn), seed, 2, strength, (0, 0, n - 1, n - 1)) def val(x, y): t = A.get((x, y)) return None if t is None else (1 if t.N == "v1" else 0) ref = {(x, 0): bottom[x] for x in range(n)} ref.update({(0, y): left[y] for y in range(n)}) for y in range(1, n): for x in range(1, n): ref[(x, y)] = fn(ref[(x - 1, y)], ref[(x, y - 1)]) filled = bad = 0 for y in range(1, n): for x in range(1, n): v = val(x, y) if v is not None: filled += 1 bad += v != ref[(x, y)] tag = "OK" if (det and bad == 0 and filled > 0) else "FAIL" print(f" rule-tile CA fn={name:3s}: directed={det} placed={filled} " f"every tile = fn(W,S) {tag}") return det and bad == 0 and filled > 0 # --------------------------------------------------------------------------- # Binary counter: each row is the row below plus one. LSB is the right column; # carry propagates west by cooperative binding (S = bit below, E = carry in). # --------------------------------------------------------------------------- def counter_tileset() -> List[Tile]: ts = [] for b in (0, 1): for c in (0, 1): ts.append(Tile(N=f"b{b ^ c}", E=f"c{c}", S=f"b{b}", W=f"c{b & c}", name=f"C b{b} c{c} -> b{b ^ c} carry{b & c}")) ts.append(Tile(N="edge", E="", S="edge", W="c1", name="edge(+1 injector)")) return ts def counter_seed(n: int): """Bottom row (y=0) all zero, plus the right-edge +1 injector column base.""" seed = {} for x in range(n): seed[(x, 0)] = Tile(N="b0", name=f"seed b0 col{x}") seed[(n, 0)] = Tile(N="edge", W="c1", name="seed edge") return seed def _test_counter(n=6, rows=None): rows = rows or (1 << n) - 1 strength = {"edge": 2} # value/carry glues default 1 A, det = grow(counter_tileset(), counter_seed(n), 2, strength, (0, 0, n, rows)) def rowval(y): bits = [] for x in range(n): t = A.get((x, y)) if t is None: return None bits.append(1 if t.N == "b1" else 0) return sum(bit << (n - 1 - x) for x, bit in enumerate(bits)) bad = filled = 0 for y in range(1, rows + 1): v = rowval(y) if v is not None: filled += 1 if v != (y & ((1 << n) - 1)): bad += 1 print(f" binary counter {n}-bit: directed={det} rows grown={filled} " f"row y encodes the integer y {'OK' if bad == 0 else f'FAIL({bad})'}") return det and bad == 0 and filled == rows if __name__ == "__main__": print("Self-assembling tile computer") a = _test_binding_gate() b = all(_test_rule2(fn, nm) for fn, nm in [(lambda w, s: w ^ s, "XOR"), (lambda w, s: w & s, "AND"), (lambda w, s: w | s, "OR")]) c = _test_counter() print("PASS" if (a and b and c) else "FAIL")