The lecture is about computational models, such as automata, which are based on a more relaxed notion of finite set. The lecture notes are in the moodle page.

Grading

Your grade will be a weighted average: 1/3 homework + 2/3 final exam.

• Homework. There are 11 homework problems, giving you up to 110 points. You get a grade according to the following table:
  • 5: ≥ 100 points
  • 4+: ≥ 90 points
  • 4: ≥ 80 points
  • 3+: ≥ 60 points
  • 3: ≥ 50 points

  You can supplement your homework score, and thus also your grade, by reporting mistakes in the lecture notes. Here you will find a recent version of the lecture notes, which you can freely annotate with mistakes that you find (first come, first serve, and please use the latest version):

  • June 11
  • June 13
  • June 21
  • June 26
  • July 3
  • July 12

  You get 1 homework point for each mistake and 2 points for each mistake in your designated chapter. (The list of designated chapter was sent by email.) That means that finding 5 mistakes in your designated chapter is the same as doing one homework problem.

• Oral exam. Below you will find a closed list of topics for the oral exam. You choose n topics from the list, and I start asking questions about your chosen topics. Assuming that you give good answers, you get a grade based on the number of chosen topics, according to the following table:
  • 5: ≥ 12 topics
  • 4+: ≥ 10 topics
  • 4: ≥ 9 topics
  • 3+: ≥ 7 topics
  • 3: ≥ 6 topics

Topics for the oral exam

Here is the closed topics, with references to the lecture notes:

1. Polynomial orbit-finite sets, and the equivalence of two representations from (Lemma 1.6).
2. Prove decidability of reachability in pof graphs  (Theorem 1.9)
3. Show that nondeterministic pof automata do not determinise, and are not closed under complementation (Theorem 2.4)
4. Show that universality is undecidable for pof automata (Theorem 2.5).
5. For the equality atoms,  show that orbit-finite sets are the same as quotiented pof sets (Theorem 4.6).
6. The least support theorem, and the accompanying representation (Theorem 4.13).
7. Definition of oligomorphic structures, and Theorem 5.7 about first-order definability.
8. Definition of homogeneous structures, and the Fraisse Theorem (Theorem 6.6)
9. Two examples of homogeneous structures: the random graph and bit vectors.
10. Prove the Finite Length Theorem (Theorem 8.5).
11. Define orbit-finite Turing machines, and show that the nondeterministic ones are expressively complete, under suitable assumptions (Theorem 9.2)
12. Prove that P ≠ NP for the bit vector atoms (Theorem 9.9)
13. Prove that Turing machines cannot be determinised for the equality atoms (Theorem 9.13)
14. Define representable sets, and show that equality is decidable for them (Theorem 10.11)
15. Define while programs with atoms, and show implication 1 => 2 in Theorem 11.2.