Fall 2022
EECS 2001 3.00 B
Introduction to the Theory of Computation
 


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: 

Microsoft Word - 2017-2018 Mini Calendar.docx

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

Microsoft Word - 2017-2018 Mini Calendar.docx

Learning Outcomes for the course:

  • Design machines (e.g., finite automata, URMs) to solve specified decision problems or compute specific functions.
  • Design regular expressions and automata for a given language.
  • Explain why an object designed in bullets (1) or (2) correctly meets its specification.
  • Prove simple properties about models of computation (e.g., that the class of regular languages is closed under complement).
  • Demonstrate limits of computing by proving that a problem is not solvable within a particular model of computation.
  • Prove impossibility results by showing how one problem can be reduced to another.

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%)
60%
Final Exam 
40%

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.


The concept of "late assignments" does not exist in this course (solutions are posted on the due date).
Last date to drop a Fall 2022 (3 credit) course without receiving a grade is November 11, 2022.  From Nov. 12 to Dec. 6 (end of classes) a student may also drop a course but this course will be flagged "W" in the transcript.

Last revised: Sep 2, 2022