Department of Computer Science State University of New York at Buffalo CS 496: INTRODUCTION TO THE THEORY OF COMPUTATION Semester: Fall 1986 Instructor: William J. Rapaport Time: MWF 11-11:50 Office: Bell 214 Room: O'Brian 112 Phone: 636-3193 Office Hours: tba & by appointment Email: rapaport TEXT: Davis, Martin D., and Weyuker, Elaine J., Computability, Complex- ity, and Languages: Fundamentals of Theoretical Computer Science (Orlando, FL: Academic Press, 1983). TOPICS: +o ``Theoretical computer science is the mathematical study of models of computation. As such, it originated in the 1930s, well before the existence of modern computers, in the work of the logicians Church, Goedel, Kleene, Post, and Turing. This early work has had a profound influence on the practi- cal and theoretical development of computer science. Not only has the Turing-machine model proved basic for theory, but the work of these pioneers presaged many aspects of com- putational practice that are now commonplace and whose intellectual antecedents are typically unknown to users. Included among these are the existence in principle of all- purpose (or universal) digital computers, the concept of a program as a list of instructions in a formal language, the possibility of intepretive programs, the duality between software and hardware, and the representation of languages by formal structures based on productions.'' (Davis & Weyucker, p. xiii). +o The basic questions of Theory of Computation are: What does it mean to say that a task is ``computable''? What is an algorithm? Are there tasks that cannot be computed? What are the limits of computation? +o We shall study the nature of formal languages, finite auto- mata, computable functions, recursive functions, Turing machines, and other topics as time permits. MECHANICS OF THE COURSE: +o You will be expected to attend all classes, and to complete all readings and assignments on time. There will be regular homework assignments, a midterm exam, and a final exam. No programming will be required. +o The final course grade will be determined on the basis of the following requirements with weights as indicated: Recitation Assignments 1/3 (including attendance, homeworks, quizzes, etc.) Midterm Exam 1/3 Final Exam 1/3 ------------------------------------------------------------------------- HOW TO READ (A MATH TEXT) S L O W L Y For each sentence do: Read it, SLOWLY. If you do not understand it, then begin re-read the previous material, SLOWLY; re-read the incomprehensible sentence, SLOWLY; if you still don't understand it, then ask a fellow student to explain it; if you still don't understand it, then ask the TA; if you still don't understand it, then ask me end; else: read the next sentence; goto step 2. ------------------------------------------------------------------------- TENTATIVE SCHEDULE OF TOPICS AND READINGS Sep. 3: Introduction to Theory of Computation Sep. 5 - Sep. 10: Ch. 1: Preliminaries Sep. 10 - Sep. 19: Ch. 8: Regular Languages Sep. 22 - Oct. 3: Ch. 9: Context-Free Languages (selected topics) Oct. 6 - Oct. 14: Ch. 2: Programs and Computable Functions Oct. 14 - Oct. 24: Ch. 3: Primitive Recursive Functions Oct. 24 - Oct. 31: Ch. 4: A Universal Program Nov. 3 - Nov. 12: Ch. 5: Calculations on Strings Nov. 14 - Nov. 24: Ch. 6: Turing Machines Nov. 24 - Dec. 1: Ch. 7: Sect. 7: Recursion and Minimalization Dec. 1 - Dec. 5: Ch. 13: Loop Programs and the Eliminability of goto Dec. 8: Ch. 10: Sect. 1: The Chomsky Hierarchy of Languages Dec. 10 - Dec. 12: Review NOTES: (1) Tuesday, Oct. 14 := Monday (2) Friday, Oct. 17 = MIDTERM EXAM (3) Friday, Oct. 24 = last R day