Reproduce “The tile assembly model is intrinsically universal” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Damien Woods
A single finite tile set is shown to intrinsically simulate every system in the abstract Tile Assembly Model, including arbitrary target temperatures, asynchronous growth, local glue interactions, and nondeterministic choices. The construction runs at fixed temperature 2 and represents each simulated tile by an O(g^4 log g)-scale supertile, where g is the number of target glues.
Key insights
- Intrinsic universality requires reproducing assembly dynamics—not merely computing the same final shape or simulating a Turing machine—so the simulator must preserve valid transitions and exclude invalid ones.
- Copying the complete target-system encoding onto every output side lets each new supertile independently evaluate local binding conditions, while frames and precedence rules manage incomplete or competing inputs.
- Opposing probes can create two output crawlers, but shared input information and synchronized random choices ensure that both encode the same simulated tile; otherwise, symmetry breaking leaves one responsible crawler.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.