Day | Time | Location Mon: Keele DB 0001 ------------------------ Wed: Keele CB 121 |
|||
Monday and Wednesday | 1:00-2:30 pm [See also Lecture Schedule ] |
Instructor: | Professor
G. Tourlakis Office: 2051 LAS, Telephone: 736-2100-66674, e-mail: gt@cse.yorku.ca |
|
Start date: | Sep. 7, 2022 |
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., 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: Oct 26, 2022, 1:00-2:20pm.
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 Counseling and Disabiliy
Services.
Last revised: Sep 2, 2022