Course syllabus

Jump to today

Models of Computation

Telegraphic course info:

Instructor: Rasmus Blanck (please get in touch by email if you have any questions: rasmus.blanck@gu.se)

Literature: Introduction to the Theory of Computation by Michael Sipser, 3rd edition, 2013.

Examination: Oral presentation (<45 min) of a topic relevant for the course, a few (3) hand-in assignments, and a short (3-5 pages) course paper on a topic chosen in consultation with the instructor.

Schedule: Available on TimeEdit. First meeting/lecture on Wednesday 18 January 10:15-12:00 in J442.

Formal course syllabus: Accessible using this link.

Lecture plan:

  • 18 Jan: Welcome, planning, intro lecture
  • 25 Jan: Rasmus: Deterministic finite automata (Please read Sections 1.1 & 1.2 before this meeting. Chapter 0 contains some additional background material that could also be useful.)
  • 1 Feb: Rasmus: Regular expressions + equivalence with DFAs (Please read Section 1.3 in advance)
  • 8 Feb: Bente: Pumping lemma for DFA (Please read Section 1.4 in advance) + Vetle: Push-down automata (Section 2.2)
  • 15 Feb: Teresa: Context-free grammars (Section 2.1) + Rasmus: Equivalence of CFGs and PDAs.
  • 22 Feb: Rasmus: more on the equivalence of CFGs and PDAs.
  • 1 Mar: Rasmus: Recursive function theory 1 (3.1, 4.1, 5.1 + slides) + Yichi: Register machines
  • 8 Mar: Recursive function theory II (5.3, 6.1, 6.3) + Time complexity I (7.1-7.2)
  • 15 Mar: Time complexity II (7.3-7.4) + Space complexity (8.1-8.2)

 

Other topics that could be suitable for a presentation or the course paper:

  • Hilbert's 10th problem (section 3.2 -- there's also the great paper Hilbert's Tenth Problem is Unsolvable by Martin Davis)
  • Variants of Turing machines (section 3.3)
  • Elementary cellular automata as a model of computation (I don't have a great reference for this right now, but Google can be your friend :-) )
  • If you want to get more philosophical, the computational theory of mind could be an interesting topic (you could start by having a look at https://plato.stanford.edu/entries/computational-mind/)
  • Other topics are fine too -- please get in touch if you have something in mind.

Course summary:

Course Summary
Date Details Due