Simulating computational complexity
summary
Claims that simple cellular automata generate rich, sometimes irreducible behavior with concrete examples: 256 elementary rules (Wolfram) produce Rule 90’s Sierpinski-like pattern and Rule 30’s apparently nonrepeating sequence, gliders in Conway’s Game of Life produce pulses (one every ~30 generations) and combined gates yield computation, and Rule 110 is Turing-complete. Practical work at ING includes Baker, an open-source orchestration library by Apollo that models API flows and exports Petri nets — a tool that proved usable for regaining system visibility.
AI-written summary · about
chapters (18)
- 0:00Computational complexity beauty
- 2:22Conway's Game of Life demo
- 3:49Complexity from simple rules
- 4:36Complex systems in nature and finance
- 5:40Cellular automata basics
- 6:44Rule-based evolution
- 7:52Rule 90 and Pascal's triangle
- 8:56CA behavior classification
- 9:39Rule 30 and irreducibility
- 10:48Gliders as binary signals
- 11:56Logic gates and Turing completeness
- 13:02CA in games and nature
- 14:11Baker at ING with state machines
- 15:59Relevance of cellular automata
- 16:43CA dimensionality and applications
- 17:45CA modeling challenges
- 18:32CA as complexity generators
- 19:13Philosophy and developer skills
related talks
21mHow hard can it be! Practical uses of complexity theory
12mComputation with sequences of neuronal assemblies
35mComputer Simulations of Social Behavior With Cellular Automata
20mSmale’s 18th Problem and Intelligence Science
48mReprogramming Biology
01h 32mThe cell as a computer: Turing complete and massively parallel
46mCorecursion, Codata, and Just a Little Combinatorial Game Theory
39mUnlimited Register Machines, Gödelization and Universality