This talk is a continuation of the talk from two weeks ago, but it will be independent, so please consider coming even if you didn’t attend the first part.

The plan for this second session is:

  - explain how to obtain a universally non-regular automaton (by adding one state to last time’s example),
  - explain how to encode Minsky machines using bounded-error probabilistic automata, with two-way and one-way variants,
  - explain how to encode probabilistic automata using only one random probabilistic transition,
    show the decidability of two problems: the equivalence and the finiteness problem. Both proofs rely on one observation: the reals with the addition and the multiplication form a field, and some linear algebra.