Atomic Gliders and Cellular Automata as Language Generators
summary
Defines an atomic glider as a single-cell carrier with a velocity and interaction rules, formalizes CA languages by projecting non-quiescent segments from regular initial sets, and proves deterministic one-dimensional CA can generate non-regular and non-context-free languages. Concrete construction uses four gliders from a single initial configuration to realize the language a^n b^{2n} c^n, and the paper provides formal definitions, glider composition rules and proofs showing the framework succeeds despite locality and determinism.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:24Cellular automata origins
- 3:55Formal methods on CA
- 8:12One-dimensional cellular automata and space-time diagrams
- 10:18Two captains protocol
- 13:35Atomic gliders as semantic units
- 16:43Glider interactions and language expressivity
- 21:51Glider expressivity limits
- 25:04Main contributions
- 27:10Future work
- 28:37Conclusion
- 29:19Question and answer session