This is the page for Automata and Computability - CSC 448 / CSC 2405 - Winter 2025

Lecture: Sidney Smith 2106, Mondays 11am-1pm.

Tutorial: Sidney Smith 2108, Wednesdays 11am - noon.

Instructor Office hours: SF 3324, Mondays 2-3pm.

TA Office Hours: https://utoronto.zoom.us/j/89622140396, Fridays 1-2pm (until Apr 4).

The class piazza is on the left.

Reference books:

Theory of Computation, by Sipser

	Topic
Jan 6	Computational Problems, Cardinality of sets, Countability, Diagonalization, Languages, Register Machines, DFAs (Mostly Sipser + you can read more about register machines here: https://www.cs.cmu.edu/~cdm/pdf/10-register-mach.pdf )
Jan 13	Nondeterminism, NFAs, Regular operations, characterizing regular languages by regular operations, GNFAs (Sipser)
Jan 23	Pumping Lemma, using the pumping lemma, context free grammars, algorithm for checking membership in a CFG (Sipser)
Jan 27	Chomsky Normal Form, parsing CFLs, pushdown automata, recognizing CFLs on PDAs (Sipser)
Feb 3	CFGs for PDAs, pumping lemma for CFLs, non-CFLs
Feb 10	MIDTERM IN CLASS
Feb 17	READING WEEK - NO CLASS
Feb 24	Turing Machines
Mar 3	enumerability, recognizability and undecidability of A_{TM}, some more undecidable problems, closure properties
Mar 10	Mapping reductions, undecidability from computational histories
Mar 17	Kolmogorov complexity, the recursion theorem
Mar 24	Peano arithmetic, Godel's incompleteness theorem, an unprovable theorem
Mar 31	miscellaneous advanced topics (automata and logic, learning automata) Resources: Chapter 2 and 3 of this survey and my notes