Computer Science 416/685: 

Computability Theory
Lehman College, City University of New York
Spring 2004

• Description:
  CMP 416: Computability Theory. 4 hours, 4 credits. Mathematical models of computers. Equivalence of computational models. Church-Turing thesis. Unsolvable problems. PREREQ: CMP 326.
  CMP 685: Computability Theory. 4 hours, 4 credits. Mathematical formulation of computability
  theory and abstract machine theory. Finite-state machines and Turing machines; Church’s Thesis; recursive functions and recursively enumerable sets; unsolvability and the Halting problem.
• Textbook: Introduction to the Theory of Computation, by Michael Sipser, PWS Publishing Company, ISBN 0-534-94728-X.
• Grading: The grading for the course will be based on:
  • Homework: 25%
  • Class Participation: 10% 
  • Midterm Exam 1: 20%
  • Midterm Exam 2: 20%
  • Final Examination: 25%
    
• Assignments: Homework assignments are posted on the class website. Instead of turning in the whole problem set, each student will be responsible for presenting and writing up some of the problems.  The written solutions will be posted on the Blackboard website for the class, so, they can used by everyone to study for the exams.  Since it's hard  to write down answers that are concise and are easily readable by all, if you wish to improve a grade on any problem, you may resubmit it for grading.
  Full credit will only be given for those solutions that are correct, clear, and concise.  For programs, full credit will only be given for those that run correctly and have good documentation and programming style.  
• Exams: The exams will be
  • Midterm Exam 1: Thursday, 11 March
  • Midterm Exam 2: Thursday, 22 April
    
  • Final Exam: TBA
    
  Since the final is comprehensive, if you do better on it than on one of the midterm exams, the score on the final may replace one of the midterm scores. Note that the final will be long and difficult, so, it is an exceptionally bad idea to plan on taking advantage of this. There will be no makeup exams, and you must pass the final to pass the class.
• Honor Code: You are encouraged to work together on the overall design of the programs and homework. However, for specific programs and homework assignments, all work must be your own.
  You are responsible for knowing and following Lehman's academic integrity code (available from the Undergraduate Bulletin, Graduate Bulletin, or the Office of Academic Standards and Evaluations).
  All incidents of cheating will be reported to the Vice President of Student Affairs.
• Computer Accounts: You will be assigned a computer account on the Linux machines for work relating to this course only. More information about the computer accounts and Linux machines will be available later in the course.