The Dynamics of Computation, and the Computational Power of Dynamics

Tune in for the live stream on YouTube or Twitter.

Abstract: Recently, much to my surprise, some work from my Ph.D. thesis and the early years of my postdoc have received some new attention from people studying fluid dynamics. This induced the following talk in Barcelona at the Hypatia colloquium: 

Computers are dynamical systems, and some dynamical systems can compute. I’ll discuss how Turing machines can be embedded in continuous dynamical systems, making undecidability and uncomputability show up in unexpected places. I’ll also discuss different models of analog computation that have been considered over the years. Finally, I’ll connect dynamics to computational complexity theory, by considering the difficulty of predicting different physical and dynamical systems, some of which have algorithmic “shortcuts” and some of which seem to require explicit simulation.