COLL-S 105 Computability and Logic (Moss) (N&M) (3 cr.)

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.