Thursday, August 2, 2007

Need an N&M or a Topics Class? Consider COLL-S 105 Computability and Logic

If you are still looking for an N&M and/or a Topics course for the fall, here's one that meets both N&M and Topics requirements. Please note that this is an honors-level course: you do not have to be part of the Hutton Honors College to take the course, but undoubtedly it will be more challenging than the regular E103/E104/E105 Topics courses.

Honors Computability and Logic (COLL)
S105 26291 Lawrence Moss
TuTh 2:30-3:45pm

The theory of computation is one of the most important intellectual developments of the first half of the twentieth century. From very slender roots, a tree blossomed in the 1930's whose fruit is the development of computers as we know them. But the same tree contains thorns, as it were; these are the 'negative results' which talk about computer programs that we can never write, and true sentences which we can never prove. These results are often taken to imply fundamental limitations on what human beings can know. They are on a cultural par with other developments that came at roughly the same time: the uncertainty principle in physics, and even with Freud's notion of an unconscious which cannot know itself.

The course will be an entry point to both the mathematical theory of computation, and also to discussions of the place that the theory occupies in broader intellectual discourse.
The 'math' aspect of the course presents the theory of computation and a bit of logic related to it. Students will write programs in a new language called 1#, and learn theory by reasoning about their programs.

A math or computer science background is not really needed (but of course it would help). It is more important to enjoy solving puzzles and to be willing to immerse yourself in the world of abstract thinking. For example, would you like to write a computer program to do something "weird", such as output itself?

The course will also look critically at the uses of results and metaphors from computability theory that have found their way into cognitive science, philosophy, biology, and other areas. This will involve readings of either survey papers or popular ("Scientific American" style) articles. The idea would be to present debates as to whether the uses of computability theory are genuine or spurious.

The class will have weekly homework on the technical material. Some of the homework will involve short writing assignments. The non- technical part of the course requires two papers.

The course will be a non-traditional mathematics course covering the basic results of the theory of computability. It has several special features:

* It not only covers the results, but it delves into the interpretation of them in areas like linguistics, philosophy of mind, and biology. Students will have to write papers on these topics, for example.

* The technical material will involve a new pedagogic approach that I am developing here. In effect, students will write programs in a new computer programming language designed especially for the theoretical work. You can find more about this part of the course at

* The course will be run as a seminar, with a limited enrollment and with lots of student participation. The course will be taught at an honors level, so it will be a challenge -- but one where people will learn things on several different levels.