The lecture is about computational models, such as automata, which are based on a more relaxed notion of finite set. The lecture is based on this book, but there will be new material added this year.

There will be 3 sets of homework problems, and a final (likely oral) exam. Your grade will be a weighted average: 1/3 homework + 2/3 final exam.

 

---

Provisional plan

Polynomial orbit-finite sets and automata that use them

• polynomial orbit-finite sets and equivariant functions
• automata, such as one-way, two-way, nondeterministic
• alternating automata

Orbit-finite sets

• sets with atoms, finite supports
• orbit-finite sets and their representation
• minimisation of automata
• learning

Atoms other than equality

• oligomorphic structures and the Ryll-Nardzewski theorem
• examples such as order or the random graph

Programming with orbit-finite sets

• set builder expressions and hereditarily orbit-finite sets
• a programming language
• polynomial time

Vector spaces

• vector spaces of orbit-finite dimension
• polynomial ideals with atoms

Turing machines

• Turing machines do not determinise