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.