Course - Models of Computation MT23

Created: September 24, 2023
Updated: October 20, 2024

---

From the course webpage: “This course introduces the classical mathematical models used to analyse computation, including finite state automata, grammars, and Turing Machines.”
“A computer scientist should be able to distinguish between what can be computed and what cannot. This distinction can only be made with a good scientific model of computers and computation. This course introduces the powerful idea of using a mathematical model to analyse computation.”
“This course describes a number of different models of computation which were proposed and analysed over the past century. Many of these models were found to be equivalent, in the sense that they allow exactly the same computations to be carried out. Other models were shown to be less powerful, but simpler to implement, and so useful for some purposes.”

• Course Webpage
• Lecture slides:
  • 1. Deterministic Finite Automata
  • 2. Non-deterministic Finite Automata
  • 3. Regular Expressions
  • 3.5. Kozen’s Axioms
  • 4. Pumping Lemma and Myhill-Nerode Theorem
  • 5. Context-Free Grammars
  • 6. Non-determinsitic Pushdown Automata
  • 7. Turing Machines
  • 7.5. Algorithms
  • 8. Decidability
  • 8.5. More on Decidability
  • 9. Computational Complexity
• Other courses this term: [[Courses MT23]]^U
• Related blog posts:
  • [[FRACTRAN and theoretically cheating at your A-levels]]^B

Notes

• [[Notes - Models of Computation MT23, Basic definitions]]^U
• [[Notes - Models of Computation MT23, Complexity]]^U
• [[Notes - Models of Computation MT23, Context-free grammars]]^U
• [[Notes - Models of Computation MT23, DFAs]]^U
• [[Notes - Models of Computation MT23, Decidability]]^U
• [[Notes - Models of Computation MT23, Kozen’s axioms]]^U
• [[Notes - Models of Computation MT23, Languages]]^U
• [[Notes - Models of Computation MT23, Myhill-Nerode theorem]]^U
• [[Notes - Models of Computation MT23, NFAs]]^U
• [[Notes - Models of Computation MT23, NPDAs]]^U
• [[Notes - Models of Computation MT23, Post correspondence problem]]^U
• [[Notes - Models of Computation MT23, Pumping lemma]]^U
• [[Notes - Models of Computation MT23, Regular expressions]]^U
• [[Notes - Models of Computation MT23, Regular languages]]^U
• [[Notes - Models of Computation MT23, Rice’s theorem]]^U
• [[Notes - Models of Computation MT23, Turing machines]]^U

Problem Sheets

• Sheet 1
• Sheet 2
• Sheet 3
• Sheet 4
• Sheet 5

Lectures

• [[Lecture - Models of Computation MT23, I]]^U
• [[Lecture - Models of Computation MT23, II]]^U
• [[Lecture - Models of Computation MT23, III]]^U
• [[Lecture - Models of Computation MT23, IV]]^U
• [[Lecture - Models of Computation MT23, V]]^U
• [[Lecture - Models of Computation MT23, VI]]^U
• [[Lecture - Models of Computation MT23, VII]]^U
• [[Lecture - Models of Computation MT23, VIII]]^U
• [[Lecture - Models of Computation MT23, IX]]^U
• [[Lecture - Models of Computation MT23, X]]^U
• [[Lecture - Models of Computation MT23, XI]]^U
• [[Lecture - Models of Computation MT23, XII]]^U
• [[Lecture - Models of Computation MT23, XIII]]^U
• [[Lecture - Models of Computation MT23, XIV]]^U
• [[Lecture - Models of Computation MT23, XV]]^U
• [[Lecture - Models of Computation MT23, XVI]]^U

---

Related posts

• [[Notes - Models of Computation MT23, Regular languages]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, XII]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Myhill-Nerode theorem]]^U

  (incoming)
• [[Notes - Models of Computation MT23, NFAs]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Pumping lemma]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Post correspondence problem]]^U

  (incoming)
• [[About this website]]^B

  (incoming)
• [[Notes - Models of Computation MT23, Turing machines]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Regular expressions]]^U

  (incoming)
• [[Notes - Models of Computation MT23, DFAs]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, XIV]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Rice's theorem]]^U

  (incoming)
• [[Courses MT23]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Decidability]]^U

  (incoming)
• [[University Notes]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Context-free grammars]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Basic definitions]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, XVI]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Languages]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, XV]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Complexity]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, XI]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, XIII]]^U

  (incoming)
• [[Notes - Logic and Proof MT24, Regular languages]]^U

  (incoming)
• [[Notes - Models of Computation MT23, Kozen's axioms]]^U

  (incoming)
• [[Notes - Models of Computation MT23, NPDAs]]^U

  (incoming)
• [[Lecture - Models of Computation MT23, I]]^U

  (sim: 0.638)
• [[Lecture - Models of Computation MT23, II]]^U

  (sim: 0.607)
• [[Lecture - Models of Computation MT23, X]]^U

  (sim: 0.6)