Syllabus - Computability and Logic

Introduction

This course covers basic concepts and results in mathematical logic and computability, including soundness and completeness of propositional and first-order logic, Turing Machines, Church’s Thesis, the halting problem, undecidability of first-order logic, Godel’s incompleteness theorem, and the undecidability of arithmetic.

Learning Objectives

At the end of this course, students will be able to:

Texts

"Language, Proof, and Logic", 2nd ed., Dave Barker-Plummer, Jon Barwise, and John Etchemendy

Exams/Grading

Your grade will be determined by a number of homework problems (75% total), a final project (20%), and class participation (5%).
Attendance is mandatory: 1% penalty per class missed
The instructor reserves the right to decide borderline cases based on exceptional class participation, unrepresentative performance, or other such factors.
Late submissions will only be accepted in case of documented emergencies for which you will have to contact the Dean of Students Office (DOSO)
After spring break, students will receive a mid-semester assessment through RPI LMS, indicating the student’s grade in the course up to that point.

Academic Honesty

Student-teacher relationships are built on trust. For example, students must trust that teachers have made appropriate decisions about the structure and content of the courses they teach, and teachers must trust that the assignments that students turn in are their own. Acts which violate this trust undermine the educational process. The Rensselaer Handbook defines various forms of Academic Dishonesty and you should make yourself familiar with these. In this class, all assignments that are turned in for a grade must represent the student's own work. In cases where help was received, or teamwork was allowed, a notation on the assignment should indicate your collaboration. Submissions of any assignment that is in violation of this policy will result in getting a 0 for the assignment. The second violation will result in the automatic failure of the course. If you have any question concerning this policy before submitting an assignment, please ask for clarification.

Classroom Behavior

Please feel free to speak up at any time during this class with relevant comments or questions. However, disruptive or disrespectful classroom behavior will not be tolerated. Also, please do not use your smartphone, laptop, or other tools of mass distraction.