Comp Sci 2MJ3: Theory of Computation
Fall 2009

• Instructor: Michael Soltys, email: my last name at mcmaster.ca
• Course Outline (Revised on September 16, 2009)
• Time: lectures on Tu, Th, Fr, 14:30-15:20, in ABB/136 (starting Friday September 18, all lectures will be in ITB-137), and tutorials:
  • T01: Mo, 11:30-13:20, JHE/210
  • T02: We, 11:30-13:20, HH/102
• Course outline: Models of computation: finite automata, regular expressions, context-free grammars, push-down automata, and Turing machines. Relationships between these models (e.g., finite automata are equivalent to regular expressions). Determinism and non-determinism in computations.
• Textbook: Models of Computation: An introduction to computability theory, by Maribel Fernandez:
  
  
• Check this web page regularly for announcements.
• Previous versions of this course: 2006.
• Please Read: McMaster Academic Integrity Statement.

Announcements:

• Dec 2: Test 3 with solutions has been posted below.
• Nov 24: Here are the slides on primitive recursive functions.
• Nov 24: Solutions and comments to assignment 3 have been posted below.
• Nov 15: Some clarifications for assignment 3. First, in question 1 we have functions f,g,h, even though we have used those function names in the definition of primitive recursion; to avoid confustion you can rename g(x,y) as sum(x,y) and rename h(x,y) as prod(x,y). Also, rename f(x,z) to q(x,z). Doing this is not strictly necessary, but it might help you not to become confused with the f,g,h function names in the definition of primitive recursion. The inverted horseshoe in question 2 (i.e., the superset symbol) is logical implication; you might be more familiar with the right-arrow for logical implication. (Thanks to Nicholas James for pointing out those possible pitfalls.)
• Nov 9: Assignment 3 (due Nov 20) has been posted below. Also, Test 2, together with its solutions, has been posted below.
• Nov 6: Solutions (with comments) to Assignment 2 have been posted below.
• Oct 30: The document on relations has been slightly updated. In particular theorem B.4 has been restated so that we have the identity (id) function on all of X, rather than just over the domain of R. Same change in theorem B.9. Equation (B.2) has also been changed with a new definition of id (again, over X, rather than the domain of R). Lemma B.15 has been updated as well. These changes are due to Nicholas James and Michael Hebelka.
• Oct 28: Nicholas James has written a very complete set of comments to test 1; you must read them!
• Oct 25: Notes on relations. We started talking about relations last week, and we are going to finish on Tuesday.
• Oct 20: Assignment 2 has been posted below; it is due on October 30.
• Oct 20: The Wednesday tutorials have been eliminated, and instead there will be an extra hour of office time on Mondays. Thus, the new office hours will be: Mondays, 11:30-13:30 in JHE/210.
• Oct 20: Solutions to Test 1 have been posted below.
• Oct 15: Notes on PDAs by Nicholas James.
• Oct 14: Assignment 1 comments by Nicholas James have been posted below.
• Oct 10: The lecture on Friday October 9 was given by Ariel Fernandez, who conducted a review for Test 1. Ariel was asked to prepare for the web one of the problems that he did not have time to cover in the lecture; he has kindly done so: Sipser 3.11.
• Oct 6: The Monday October 12 and Wednesday October 14 tutorials will be replaced by a single tutorial on Thursday October 15 during the usual lecture time. This tutorial is scheduled in preparation for Test 1 which will take place on October 16, again during the usual lecture time.
• Oct 1: Here are notes by Nicholas James on how to make M' from M such that L(M')=L(M)*
• Sept 21: Instructor's office hours:
  • Tuesdays 1:30-2:30
  • Thursdays 1:30-2:30
  Or by appointment.
• Sept 19: Assignment 1 has been posted below.
• Sept 19: Dates for assignments and tests:

  Assignment 1	October 2
  Test 1	October 16
  Assignment 2	October 30
  Test 2	November 6
  Assignment 3	November 20
  Test 3	November 27	updated on Oct 5

  All tests will be written during the usual lecture hour in ITB-137 (which is the usual lecture room). The dates for the assignments indicate the due dates; the assignments will typically be given at least two weeks before the due date. Assignments are to be submitted during the lecture on the due date.
• Sept 18: The tutorials on Monday Sept 21 & Tuesday Sept 22 are canceled because the TA is sick. Tutorials will start therefore on September 28. Please email the TA if you have any questions or need help; the TA is Nicholas James, and his email is jamesnd2 at mcmaster dot ca.
• Sept 16: Starting Friday September 18, all lectures will be in ITB-137
• Sept 14: The lecture on Tuesday September 15 will be given by Tim Paterson. It will be a review of mathematical induction, which we are going to be using in the course.
• The TA will hold the following office hours:
  • Mo, 11:30-12:30 in JHE/210
  • Wed, 11:30-12:30 in HH/102

Assignments and Tests:

• Assignment 1 and solutions with comments.
• Test 1 with solutions and comments.
• Assignment 2 and solutions with comments.
• Test 2 with solutions.
• Assignment 3 and solutions with comments.
• Test 3 with solutions.