A significant amount of the assignments in this course involve programming. Yes, this is a theory class, but this is the theory of a practical application.

Applying your understanding of these theoretical concepts helps you to transfer this information to a familiar domain (your own favorite programming language) and acts a bridge between theory and practice. As Olivier Danvy writes:

Witness interpreters, compilers, and partial evaluators, and going all the way back to Alan Turing’s point of simulating a virtual machine with another one as well as all the way forth to the POPLmark Challenge today, there is simply nothing like computation to describe computation.

Furthermore, you should see this as an opportunity to use the skills you’ve developed in your other classes in a new domain. Beyond using some ordinary programming tools, we will not ask you for much in the way of background. Most of the work of these assignments should be internalizing the ideas and applying them in context.

We might find that some problems really do demand that we address them with formal proof. If and when those come up we will adjust, but at least for the time being plan as though you will be programming your theory of computation assignments.

To quote Alan Perlis from his Epigrams in Programming,

  1. You think you know when you can learn, are more sure when you can write, even more when you can teach, but certain when you can program.

Updated: