Universality, Hardness, Engineering, and Messiness


Add to Cal
  • Speaker: Christopher Moore (Santa Fe Institute)
  • Host Department: Physics
  • Date: 10/17/2013
  • Time: 2:00 PM - 3:00 PM

  • Location: 4448 East Hall (New Room)

  • Description:

    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.

College of Literature, Science, and the Arts 500 S. State Street, Ann Arbor, MI  48109 © 2015 Regents of the University of Michigan