‘Models of Computation’ is an intensive block course for students who are interested in learning about a variety of existing models of computation and how to analyze such models.
This course will provide a survey of models such as Turing Machines, Cellular Automata, Graph Automata, Lambda Calculus, Tiling Systems, Chemical Reaction Networks, and many more. The goal is to understand, through examples, computation in a broader sense, so that we can recognize it even when it looks nothing like a traditional computer program.
For example, we would like to understand the brain. There is one key reason why Artificial Intelligence has failed so far to live up to the naive expectations of reproducing human intelligence, and that is this: We have a terribly poor understanding of the computation that goes on in the brain and we are completely unable to simulate it, despite decades of experimental data from neurobiologists. If the brain worked even remotely like a Turing machine, we would understand it by now. Similarly, if we had a computational model that worked even remotely like a brain, we would have a good understanding of the brain by now.
So, to understand the brain or biological computation, we will need to develop entirely new models of computation. It seems that the best hope for developing these new models is the following:
1. Understand a variety of existing models of computation.
2. See how these models are similar to and different from each other, and similar to and different from the kinds of desirable computation that we have not yet been able to model.
3. Do our best to try to create models that are closer to brains or biology than existing models.
This course gives students a deeper understanding of (1) and (2), to help prepare them for doing (3) in their scientific career.