Algorithms and Computability
Course Management Form, Fall 2013
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.
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
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
includes Errata to the 2nd edition from 2003. [This is a textbook for a Ryerson course
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,
hardbound ($80), ISBN-13: 978-0123849588
Academic Press (Elsevier), 2011.
A Mathematical Introduction to Logic, 2nd edition,
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.
Taylor&Francis, CRC Press, 469 pages.
Uwe Schoning ``
Logic for Computer Scientists", published by Birkhauser, Boston 2008
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.
Policy on collaboration in homework assignments
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.
Limited collaboration in discussing general approaches to problems
is allowed; no collaboration is allowed when you are typing or
writing your solutions. You may discuss assignments only with other people
currently taking the course or with the instructor.
However, you should never put your name on anything
you do not understand.
you must be able to reproduce and explain all solutions by
yourself. If you cannot explain a solution that you handed in,
this will decrease your mark.
The first page of your homework should include: the name of all
students with whom you discussed any homework problems (even briefly).
Otherwise, it is assumed that you didn't discuss with anyone except the
instructor. Copied work (both original and copies) will be graded as 0.
Tentative Course Calendar
(all changes of dates will be announced)
||Grade Value (%)
September 18 & September 25, Wednesday
October 9, Wednesday
Wednesday, October 23, in class
October 30, Wednesday
November 13, Wednesday
November 27, Wednesday
Wednesday, December 4, in class
In class (topic to be assigned)