COMPLEX SYSTEMS SEMINAR | Universality, Hardness, Engineering, and Messiness

I will review some of the ways that dynamical systems can carry out universal computation, such as simulating Boolean circuits with cellular automata and sandpiles, and simulating Turing machines with iterated maps or flows in low-dimensional chaotic systems. I will then comment on the fact that our proofs that natural systems are hard to predict or understand (undecidability, NP-completeness, etc.) all rely on an ability to "build a computer" in those systems. These systems are hard to predict, but easy to think about in the sense that we can do engineering in them, designing gadgets that store and transmit information in controlled ways. In contrast, many natural systems seem very messy, with lots of complicated dynamics, but complicated in a way that makes it hard to imagine building a computer out of them. Predicting these messy systems might lie in the gap between decidability and Turing-completeness.