| Day | Time | Location Mon: Keele ACW 005 ------------------------ Wed: Keele ACW 005 |
|||
| Classes Monday and Wednesday |
10:00am-11:30am |
||||
| Tutorials Fridays |
9:00am-10:30am | Fri: Keele LSB 103 |
|||
| Instructor: | Professor
G. Tourlakis Office: 2051 LAS, Telephone: 736-2100-66674, e-mail: gt@cse.yorku.ca |
|
| Start date: | Jan. 5, 2026 | End date:
April 6, 2026 |
It is the responsibility of students to check the course web page weekly for course related information.
COURSE DESCRIPTION
This is a first course on the theoretical
limitations of computing: That is, what we cannot do by programming. On the other
hand, some topics (e.g., Finite Automata) find application in a
wide variety of areas in the field (e.g., software engineering,
developing compiler writing tools), however, "application" is not the
main focus of the course.
Topics will include in approximate chronological sequence: A
General Mathematical Model of Computation (e.g., An Extremely
Simplified C-like programming Language called the URM);
Church's Thesis and Kleene's SMN Theorem; problems that the
general model can
solve and problems it cannot solve:
diagonalisation and reductions towards proving that certain
problems -- such as the "Program Correctness" -- cannot be solved by our model (same as:
cannot be programmed in our
model). We then look into Restricted Models of Computation: Formal
Languages, their deciders
and verifiers, and their
limitations.
Specifically, the following themes: Regular languages
and Grammars and finite
automata. The focus will
be on what these restricted models of computation cannot do: Impossibility results via the
pumping
lemmata.
PREREQUISITES:
General
prerequisites; LE/EECS1021 3.00 or LE/EECS1022 3.00 or
LE/EECS1720 3.00 or LE/EECS1030 3.00;
LE/EECS1028 3.00 or SC/MATH1028 3.00 or LE/EECS1019 3.00
or SC/MATH1019 3.00
Learning Outcomes for the course:
REQUIRED TEXT
G. Tourlakis, Theory of Computation
, John Wiley & Sons. ISBN: 9781118014783.
AUXILIARY SUGGESTED SOURCES
H. R. Lewis and C. H. Papadimitriou, Elements of the Theory
of Computation, Prentice Hall (latest edition). ISBN 013
2734176
Michael Sipser, Introduction
to
the Theory of Computation, PWS Publishing Company. ISBN
0-534-94728-X
WEIGHTING OF COURSE
| Term work (Homework 30% ; Mid-Term Test 30%) |
|
|
| Final Exam |
|
Mid Term Test Date/Time: TBA.
Note:
Missed tests with good reason
(normally medical, and
well documented) will have their weight transferred
to the final exam. There are no "make up" tests and no makeup assignments. Tests
missed for no reason are deemed
to have been written and are marked "0" (F). The weight of a missed
assignment is never carried
to the final. A mid
term test or homework assignment that is written and marked cannot
be "erased" by moving its weight to the final exam.
The
homework must
be each individual's own work. While consultations
with the instructor, tutor(s), and among students, are part of the learning process and are encouraged, nevertheless,
at the end of all
this consultation each
student will have to produce an individual (typed)
report rather than a copy
(full or partial) of somebody else's
report.
Follow these links to familiarise
yourselves with Senate's and Lassonde School's expectations
regarding Academic Honesty, and Academic
Integrity. Please also familiarise yourself with many
other Senate policies, in particular, with those about https://www.yorku.ca/secretariat/policies/policies/academic-accommodation-for-students-with-disabilities-guidelines-procedures-and-definitions/,
Religious
Accommodation, https://www.yorku.ca/secretariat/policies/policies/cross-listed-courses/
Please also check these two
links! Student
Rights
and Responsibilities and SAS.
Last revised: Dec 9, 2026