This talk is about probabilistic automata over finite words: such machines, when reading a letter, flip a coin to determine which transition to follow. Although quite simple, this computational model is quite powerful, and many natural problems are undecidable.

In this talk, I will review some of the most important undecidability results, with new simplified constructions.