Lehman College, City University of New York

Fall 2016

**Description:**

- CMP 416: Computability Theory.
*4 hours, 4 credits.*Mathematical formulation of computability theory and abstract machine theory. Finite-state machines and Turing machines; Church-Turing Thesis; recursive functions and recursively enumerable sets; unsolvability and the Halting Problem.*Prerequisites*: CMP 232 and 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.

**Undergraduate vs. Graduate Sections:**
The lectures for the undergraduate and graduate courses will be the same, but the class work, assignments, and exams of the two courses are different. While both the undergraduate and graduate courses assume fluency in a procedural programming language and discrete mathematics, the graduate course requires graduate-level programming skills and mathematical proofs.

- Problem Sets: 15%
- Class Work and Quizzes: 20%
- Midterm Exam 1: 20%
- Midterm Exam 2: 20%
- Final Examination: 25%

**Problem Sets:** 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 top three grades will make up the assignment grade for the course). 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.

**Class Work and Quizzes: ** Every class meeting there will be graded work or quizzes. There are 26 class meetings and 2 midterm exams over the course of the semester. The top 20 grades earned will make up the class work grade. The Blackboard honesty pledge quiz can also count for this grade if submitted by Friday of the first week.

**Exams:** The exams will be

- Midterm Exam 1: Thursday, 29 September
- Midterm Exam 2: Tuesday, 8 November
- Final Exam: Thursday, 15 December

**Honor Code:**

- You are responsible for knowing and following Lehman's academic integrity policy (available from the Undergraduate Bulletin, Graduate Bulletin, or the Office of Academic Standards and Evaluations).
- 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.
- All incidents of cheating will be reported to the Vice President of Student Affairs.

**Textbook:** *Introduction to the Theory of Computation*,
by Michael Sipser, Cengage Publishing, any edition (about $40 for second edition).

**Use of Technology & Blackboard:** All coursework is submitted via the Blackboard system, provided by CUNY to all enrolled students. If you have not accessed Blackboard or are having difficulties, contact
Blackboard Support in the Information Technology Division. You can also visit the Help Desk in the Computer Center (first floor, Carman Hall) in person. They can reset passwords and help with simple Blackboard issues.

**Accommodating Disabilities: ** Lehman College is committed to providing access to all programs and curricula to all students. Students with disabilities who may need classroom accommodations are encouraged to register with the Office of Student Disability Services. For more information, please contact the Office of Student Disability Services, Shuster Hall, Room 238, phone number, 718-960-8441.

- Describe finite state automatas and regular languages, and show their equivalence.
- Explain and use regular expressions ("regex") both theoretically and in parsing strings.
- Use the pumping lemma for both regular and context-free languages.
- Define decidability and solvability.
- Describe a Turing Machine and the Halting Problem.
- Use Big-oh notation to analyze algorithms.

- Explain the Church-Turing Thesis.
- Prove the Halting Problem is undecidable.
- Demonstrate the difference between Big-oh and Small-oh notation in the analysis of algorithms.

This website for this class is located at:
http://comet.lehman.cuny.edu/stjohn/teaching/comptheory/f16.html