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.