What does it mean to compute? People have struggled with this question for a long time, and many models of computation have been invented. These models guide our thinking about what it means to compute.

This class will survey many different models of computation.... Turing Machines, Cellular Automata, Finite State Machines, Stack Machines, Graph Automata, Lambda Calculus, Fractran, Tiling Systems, Chemical Reaction Systems, Hopfield Networks, Boltzmann Machines, Neural Networks, Circuits, Graphical Models, Boolean Algebra, String Rewriting Systems, Semigroups, Quantum Waves, Diophantine Equations, Tag Systems, etc., etc. (This list is meant to give the flavor -- actual topics covered will vary slightly from year to year.)

In this class, our 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, and so that we can think about and even create computational models that are not close to computers.

These models are fun, but there are also more serious reasons to be interested in models of computation.

For example, we would like to understand the brain. There is one key reason why Artificial Intelligence has struggled 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. We are completely unable to simulate it, and we cannot even recognize what the general form of this computation is, 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. The problem is that we are incapable of understanding the brain so long as we have no model of computation that works anything like the brain does.

Similarly, we do not understand biological programs. We cannot recognize a program to build a rose even if we have access to the full source code (the dna). We are starting to have some clues how these programs work, and the field of synthetic biology is starting to tackle the problem of how to create working programs, but we are still largely in the dark. Today, we cannot be sure whether even the smallest of our synthesized biological programs will work as intended, and systems of the size presented by biology are still a distant pipe dream. Again, the key problem is that we have no models of computation that are appropriate to this setting. We don't even have any idea how to define whether a program to build a rose has produced the correct output or not, since every rose is different, even when made from the same dna. Lacking models that we can analyze, we don't know which properties of these biological systems are resposible for their robustness, and we are unable to distill the key principles into scalable models that permit analysis.

So, to understand the brain or biological computation, we will need to develop entirely new models of computation. (Different ones for brains than for biology.) Of course, it is not clear yet what these new models should be. Our best hope for developing 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.

With any luck this stochastic gradient ascent will eventually get close enough that the models start to pay off by allowing productive theoretical analysis of the processes in question, allowing us to develop principles that allow us to scale up similar systems of our own engineered design.

This class will help with (1) and (2) above. Then (3) is up to you, in your scientific career.