Comp 230: Logic and Computability, Fall 2017 


Aim of the course: To introduce students to the theoretical foundations of computer science. Since students are not expected to have taken a logic course before, the course will include an introduction to propositional and predicate calculus. Other topics are proof systems, computability, Turing machines, Church-Turing thesis, unsolvable problems, completeness, incompleteness, Tarski semantics, uses and misuses of Gödel's theorem.
Prerequisites: Mathematics at CEGEP-level. Not open to students who have done PHIL 310 or MATH 498.
Textbooks: The following textbook is required for this course.
  • Douglas R. Hofstadter, Gödel, Escher, Bach, 20th Anniversary Edition, 1999.
The book is available at The Word Bookstore, 469 Milton Street (5 mins. from the University Street Gates; no credit cards).

Additional reading materials will be on course reserve, available online or handed out in class.
Requirements & grading: Students are expected to attend and participate in class, do the assigned readings, complete homework assignments, and write three in-class quizzes, a midterm, and a final exam.

The final grade depends on homework assignments (not graded) (5%), three in-class quizzes (10% each), a midterm (25%), and a final exam (40%). Every student can take up to two "late days" for handing in the homework assignments during the semester. Otherwise, late homework will not be accepted (except in cases of documented emergencies).
Academic integrity: McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see  for more information).

Home Syllabus Schedule Links (c) Dirk Schlimm   9/04/2017