1D Cyclic Tag Turing Machine Wolfram/Smith (2,3)
2 States (q₁, q₂) • 3 Symbols (Σ = {0, 1, 2}) • 6 Transition Tuples
2D Planar Turmite Studio Langton's Ant
Planar Grid • Discrete Rotation (±90°) • 104-Step Emergent Highway
2D Spatial Logic Gate Constructor (Glider Collision Schematic)
Based on Gajardo et al. (2002): Constructing Boolean Logic (AND, NOT) via deterministic 2D ant trajectory interactions.
Signal Generators
Emergent Truth Table
| A | B | AND (A ∧ B) | Deflected (A ∧ ¬B) |
|---|---|---|---|
| 0 | 0 | 0 (No Highway) | 0 (No Deflection) |
| 1 | 0 | 0 | 1 (Deflected Stream) |
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 (Combined Highway) | 0 |
The Universality Continuum (Section 4.2 Technical Commentary)
Historical reduction from Turing's direct arithmetic machines to minimal tag systems and 2D spatial automata.
Explicit transition rules direct every computation directly in internal state logic.
Compiles algorithms into tape data via 2-tag deletion and production rules.
Offloads computational logic into an infinitely periodic cyclic tag tape stream.
Replaces tape head scanning with 2D spatial collision and highway dynamics.
Formal Architectural Comparison
| Dimension | Small 1D Cyclic UTM (2,3) | 2D Planar Turmite (Langton's Ant) |
|---|---|---|
| Memory Geometry | Infinite 1D linear tape (ordered array of symbols) | 2D unbounded discrete planar lattice (ℤ × ℤ) |
| Head Movement | 1D discrete translation: {L, R} | 2D discrete rotation and translation: {Turn ±90°, Step} |
| Control State | 2 internal control states (q₁, q₂) | Spatial orientation vector (D ∈ {N, E, S, W}) |
| Universality Mechanism | Cyclic tag system simulation & symbol rewriting | Emergent 2D trajectory collisions and logic gates |
VAL Scoping & Evaluation Testbed (Section 4.3 Specifications)
Structured formal prompts for RMIT's in-house generative AI tool with a 4-stage academic verification pipeline.
"Act as a theoretical computer science tutor. Given a 2-tag system with alphabet {a,b} and deletion number 2, provide the step-by-step mathematical trace for transforming w = aabb into a (7,4) Minsky TM tape..."
"Summarize the core mathematical debate between Wolfram/Smith and academic critics regarding the universality of the (2,3) Turing machine. Detail the role of cyclic tag encoding..."
"Construct the complete formal 2-state, 2-color Turmite transition function delta(q, c) -> (q', c', d) reproducing Langton's Ant. Verify logic gate computability..."
"Derive a formal Pumping Lemma proof showing why a 2-state FA cannot distinguish balanced parentheses aⁿbⁿ, whereas a 2-state TM with tape rewriting capabilities can."
Four-Stage Evaluation Pipeline
Execute structured prompt to generate theoretical derivations and state transition sequences.
Cross-verify every state tuple δ(q, s) against Linz (2016) and Minsky (1962).
Stress test output against counter-example words and edge boundary inputs.
Feedback detected gaps into targeted prompts for finalized formal proofs.