Sat Mar 12, 2011
60 Evans Hall, 12:10–2 AM
Bjørn Kjos-Hanssen (Associate Professor of Mathematics, University of Hawaii at Manoa)
Discerning Randomness from an Asymptotic Hamming Distance
A notion of asymptotic Hamming distance suitable for the study of algorithmic randomness of infinite binary sequences is developed.
As an application, it is shown that there is no fixed procedure that computes a (weakly) Mises-Wald-Church stochastic sequence from an arbitrary complex sequence. Here a sequence is complex if its fixes have Kolmogorov complexity bounded below by an unbounded, nondecreasing computable function.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).