1Welcome!
Welcome to the website for the second half of COMP30026 Models of Computation!
This website contains the companion notes to my lectures and other resources. There is a lot of dense information, putting all of them up on the slides can be visually overwhelming. Thus, I have designed my slides to only contain information pertinent to the focus of the lecture. You are welcome to open up the website on your laptop or phone (it’s actually mobile-friendly) to use as a reference during the lecture.
1.1Lecture schedule¶
| Lecture | Topics Covered (Topic Numbers) | |
|---|---|---|
| Week 6 Lecture 1 | Finite Automata (2, 3, 4 - 4.1.5) | Slides |
| Week 6 Lecture 2 | Finite Automata (4.1.5-4.1.7), Operations on Languages (4.2), Nondeterministic Finite Automata (4.3) | Slides |
| Week 7 Lecture 1 (Cezary) | NFA Determinisation and Minimisation | Cezary’s Slides |
| Week 7 Lecture 2 (Cezary) | Regular Expressions | Cezary’s Slides |
| Week 8 Lecture 1 | Proving Nonregularity | Slides |
| Week 8 Lecture 2 | Proving Nonregularity | Slides |
| Week 9 Lecture 1 | Finite Automata Summary, Context-Free Languages, Context-Free Grammars | Sipser’s slides, Sipser’s lecture (up to 27:19) (note Sipser does not cover Sections 5.1.4 and 5.1.5) |
| Week 9 Lecture 2 | Pushdown Automata | Cezary’s Slides |
| Week 10 Lecture 1 | CFG = PDA, Summary, Introduction to Turing Machines | Slides Part 1, Slides Part 2 |
| Week 10 Lecture 2 | Church-Turing Thesis, sec-alg-reg-cfl | Slides |
| Week 11 Lecture 2 | Undecidabilty and Unrecognizability by Diagonalization | Slides |
| Week 11 Lecture 2 | Undecidabilty and Unrecognizability by Self-Reference | Slides |
| Week 12 Lecture 1 | Reductions, Closure Properties | Slides |
| Week 12 Lecture 2 | Wrap-Up |
1.2Resources¶
My materials and approach to teaching them are inspired by the following amazing books and courses. They will also be the main resource for this subject.
Introduction to Theoretical Computer Science by Boaz Barak (Harvard University)
CS 103: Mathematical Foundations of Computing (Stanford University)
Notes on Models of Computation by Jeff Erickson[1] (UIUC)
Introduction to the Theory of Computation by Michael Sipser is a great textbook.
1.3Proofs¶
One of the biggest differences with the above resources is that writing mathematical proofs about computation is not an intended learning outcome for COMP30026. Instead, our goal is to teach the key ideas and arguments behind these proofs. These can then be turned into mathematical proofs once one has learned mathematical proofs (e.g. MAST20026 Real Analysis). If you are interested in self-learning how to write proofs, check out the Resources section and lectures of CS 103 (this subject only assumes US high school algebra as a prerequisite.) and Module 1 of CS 251.
1.4Tips for success¶
The Preface of Introduction to Theoretical Computer Science has some great advice on how to succeed.
There are two pieces of advice that I want to add to the above.
Most of the time, the definitions and theorems are stated in very general terms and thus can seem very abstract. I strongly encourage you to think about some simple concrete examples of the objects in the definitions and theorems. For example, later on, we will talk about sets of bit strings; it is helpful to check your understanding by thinking about whether the set contains the empty string? What is the smallest string in the set? What is the smallest string that is not in the set? Is the set empty? Does it contain every string?
For example, when working on problems, it is useful to try to find simpler versions that you can tackle. We will provide scaffolding for problems in Assignment 2 to show you how to break down problems into simpler subproblems.
Jeff also has a wonderful Algorithms textbook that is free and available online.