Course Description

• Summary of Content: This course is on foundations of theoretical computer science. It is a junior graduate / senior undergradaute level introduction to nature and limitations of computability and logical reasoning. The first part of this course starts with the theory of (primitive) recursive functions and relations, the concept of enumerability, and the celebrated method of diagonalization used to prove the existance of nonenumerable sets. Then we are concerned with the issue of the existence of algorithms (or effective computational procedures) for solving various problems. We consider Turing machines and study an example, the halting problem, for which we prove that this problem cannot be solved by any algorithm. We consider Universal Turing Machines and equivalence of different concepts of computability. The second part of this course deals with the principal fundamental theoretical results about logic and builds on the material covered in the first part of the course. The second part includes first-order logic (syntax and semantics), the completeness theorem for first-order logic, undecidability of first-order logic, Peano Arithmetic, representability of recursive functions and Godel's Incompleteness Theorems.
• Educational Objectives: enable students to learn some of the foundations of the contemporary computer science. The existence of universal Turing machines, unsolvable problems and the Godel incompleteness theorems are among the most celebrated results in the theory of computability which are important not only in the science of digital computers but also have broad philosophical significance.
• There is no required text book. You have to take notes in class. Recommended references:
  (sorted alphabetically by the family name of first author ):
  
  • 
    A Course in Mathematical Logic by   J.L. Bell and M. Machover, hardcover ($153), 572 pages. Publisher: North Holland, 1977, ISBN-13: 978-0720428445.
  • 
    Mathematical Logic For Computer Science, 3rd edition, by  Mordechai Ben-Ari, paperback ($60), Springer, 2012, ISBN 978-1-4471-4129-7. Concentrate on Section 2.6 - 2.7, Section 7.5 - 7.6 and skip the rest. Author's Web page includes Errata to the 2nd edition from 2003. [This is a textbook for a Ryerson course MTH714 ].
  • 
    Edward A. Bender, S. Gill Williamson ``Short Course in Discrete Mathematics", Dover, 2005. ($14 on Amazon.ca). See sections on Functions and Order posted online in PDF. Alternatively, recall differences between function and relation from a short and readable overview of The Language and Grammar of Mathematics, published as Section I.2 (Part 1 "Introduction"): pages 8-16, in Timothy Gowers (Editor) The Princeton Companion to Mathematics, Princeton University Press, 2008.
  • 
    George S. Boolos, John P. Burgess, Richard C. Jeffrey   Computability and Logic , 5th Edition, Cambridge University Press, ISBN-13: 9780521877527. EBook in a PDF format is available from the publisher ($24US). Paperback ($32) is available from Amazon.ca   The 4th edition has a number of typos (previous editions have misprints, different coverage and scope).
  • 
    Computability and Unsolvability by   Martin Davis, paperback ($16), ISBN: 0486614719 , Publisher: Dover Publications.
  • 
    Computability Theory: An Introduction to Recursion Theory, 1st edition, by   Herbert Enderton, hardbound ($80), ISBN-13: 978-0123849588 Academic Press (Elsevier), 2011.
  • 
    A Mathematical Introduction to Logic, 2nd edition, by   Herbert Enderton, hardbound ($80), ISBN-13: 978-0122384523 Academic Press (Elsevier), 2001.
  • 
    Introduction to Mathematical Logic, 4th or 5th Edition, by   Elliott Mendelson , hardbound ($90), ISBN-13: 978-1584888765. Google preview. Publisher: Taylor&Francis, CRC Press, 469 pages.
  • 
    Uwe Schoning `` Logic for Computer Scientists", published by Birkhauser, Boston 2008 (Available online from the Ryerson library. A paperback edition is $33 on Amazon.com). [Skip resolution, since we consider only a semantic tableau algorithm for logical reasoning: Sections 1.1 - 1.2, and Sections 2.1 - 2.2].
  • 
    ``Mathematical Logic" (paperback) by   Joseph R. Shoenfield. Publisher: A K Peters/CRC Press, 2001, 352 pages, ISBN-13: 978-1568811352. ($46 on Amazon.ca)
  • 
    An Introduction to Godel's Theorems by   Peter Smith, paperback ($35) and eBook ($30US). Look for a 2008 corrected reprint. Cambridge University Press, ISBN-13: 9780521674539. Amazon.ca (2nd edition) ($33).
• 
  Topics (tentative list): computability theory including (Primitive) Recursive Functions and Relations, (Universal) Turing Machines, logical foundations including Syntax and Semantics of First-order Logic, Undecidability of First-order Logic, Completeness of Predicate Calculus, Peano Arithmetic, Godel's Incompleteness Theorems, Basic Complexity Theory.

Course Policies

• Examinations: The first test, and the second test may include problem solving, short essay questions as well as yes/no questions that require also a brief argument. The duration of these examinations will be 1h30min, and 2h:00min, respectively. The first test will include questions related to material covered in the first half of the course. The second test will be cumulative and will test knowledge of all material covered throughout the term, but with emphasis on the second half of the term. There will be no supplemental examinations.
• Dates are subject to change, all changes will be announced in class and on the course Web pages.
• Assignments should be submitted on or before the deadline specified in the assignment (you are encouraged to submit assignments earlier). Assignments should be handed in either as a printout (e.g., prepared with LaTeX), or legibly and clearly written.
• Each student should prepare and present a mini-lecture on a topic assigned by the instructor.
• From time to time, I will hand out exercises. The students are expected to solve the exercises, but they will not be graded. However, working on exercises will improve your understanding of this course (and will help you to get better marks on tests).
• Up to 5% extra credit may be assigned for class participation.
• Assignments will be made available on the Blackboard (my.ryerson.ca) Web site only. Also, you have to visit the course Web pages regularly. Read assignments related information that is provided or linked from these Web pages or at the Blackboard course shell. Before sending your questions by e-mail to the instructor, please check these Web pages and the Blckboard course shell whether similar questions have been already answered. The students are encouraged to attend office hours if they have questions related to their homework.
• Email communication: please send me email from local Ryerson's email addresses only. Please be aware that email sent from Yahoo, Hotmail and other popular domains can be filtered out as spam and might not reach my mailbox. Email messages will be normally answered within 24 hours, however messages received on weekend (starting from Friday evening) will be usually answered on Monday.

Tentative Course Calendar (all changes of dates will be announced)

Course Work	Due Date	Grade Value (%)
Assignment  1	September 18 & September 25, Wednesday	10
Assignment 2	October 9, Wednesday	10
Test 1	Wednesday, October 23, in class	20
Assignment 3	October 30, Wednesday	10
Assignment 4	November 13, Wednesday	10
Assignment 5	November 27, Wednesday	10
Test 2	Wednesday, December 4, in class	20
Presentation	In class (topic to be assigned)	10
		100