COSC2001 3.00 B (F20)


*Day*	*Time*	*Location* BY ZOOM ------------------------
Monday and Wednesday	1:00-2:30 pm [See also Lecture Schedule ]	*Location* BY ZOOM ------------------------


Instructor:	Professor G. Tourlakis , Office: 2051 LAS, Telephone: 736-2100-66674, e-mail: gt@cse.yorku.ca
Start date:	Sep. 9, 2020

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, Context Free Grammars) 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, the Turing Machine); Church's Thesis and Kleene's SMN Theorem; problems that the general model can solve and problems it cannot solve: diagonalisation and reductions toward proving that certain problems -- such as the "Halting Problem" -- 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 and Context free 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.

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:

Design machines (e.g., finite automata, URMs) to solve specified decision problems or compute specific functions.
Design regular expressions and context-free grammars 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.

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%

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.

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.

The concept of "late assignments" does not exist in this course (solutions are posted on the due date).