SI472 Class 1:

Reading
Martin: sections 1.1 and 1.3.

Homework
Click for Homework!

Lecture
Organizational Stuff
Hand out course policy, choose section leaders, give a word or two about the calendar, fire escape routes! Important:This class runs in the fall only, and it is a required course for graduation with a CS Degree. Thus, if you fail this course you will not be graduating next May. Keep this fact in mind!

What is "The Theory of Computation" all about?
Mechanical computation seems to involve two things: a machine for performing computations, and a language for communicating input/output with the machine, and indeed those are the two basic objects of study in the theory of computation. The really surprising thing is that the computational power of a mchine seems to correspond directly to the type of language it can recognize, so that these two subjects are actually two sides of the same coin.

The language of the course: sets, logic, functions
Sets, logic, and functions provide the language with which we'll discuss computation and languages. This lecture will focus on sets: Lecture Notes for Sets

Because nobody beleives me that anyone doing computer science needs/uses something as silly as sets and this wierd notation for defining sets, I cut this paragraph

out of: Cheer-Sun Yang and Lori Pollock, ``An All-du-path Coverage Algorithm for Testing Shared memory Parallel Programs'', The Sixth Asian Test Symposium, November 1997. This is a research paper on an algorithm for automated testing of parallel computer programs. This is very much a "systems" area of research, rather than a "theory" area of research, yet those pesky sets crop up none the less.


Asst Prof Christopher Brown
Last modified: Wed Aug 23 10:30:50 EDT 2000