# Andre Nies: Randomness and computable analysis, Alex Simpson: From the measure algebra isomorphism theorem to optimal data compression

Source: Mathematics and theoretical computing seminar

Tokrat bomo imeli "dvojni" seminar skupaj s seminarjem za Diskretno matematiko. Od **10h do 12h** bo predaval Andre Nies iz Univerze v Aucklandu, Nova Zelandija, o* "Randomness in Computable Analysis"*. Od

**12h do 14h**bo predaval Alex Simpson iz Univerze v Edinburghu, Škotska, o

*.*

**"From the measure algebra isomorphism theorem to optimal data compression"****Povzetek predavanja Alexa Simpsona:** The classical "measure algebra isomorphism theorem" (attributed variously to Wiener, Caratheodory, Maharam, von Neumann and Halmos) asserts that the lattice of measurable subsets of [0,1], quotiented modulo null symmetric difference, is characterised up to (measure-preserving) isomorphism as the unique separable non-atomic (strictly positive) measure algebra.

I will start the talk with a slight variation on this result that characterises the lattice of *open* subsets of [0,1] modulo null in lattice-theoretic terms. The benefit of the variant result is that its proof is "constructive". Nevertheless, I shall present the proof in a way that presupposes no knowledge of constructive mathematics.

By interpreting the constructive theorem in a suitable model (a "realizability topos"), one automatically obtains a "computable" version of the variant theorem. Here, again, I shall assume no knowledge of the (somewhat elaborate) machinery used in this process, but will merely state the theorem that results in concrete terms.

Finally, I shall interpret the extracted theorem in the special case of a lattice constructed from a Markov chain that probabilistically generates infinite words over a finite alphabet. In this case, the computable content underlying the measure-preserving isomorphism produced by the theorem corresponds exactly to an algorithm for compressing the probabilistically generated data stream using the method of "arithmetic coding", which is an information-theoretically optimal method of data compression.

Vabljeni!