Oscillation-Free Epsilon-Random Sequences

Ludwig Staiger (Martin-Luther University Halle-Wittenberg)

CECS SEMINAR SERIES

DATE: 2013-03-18
TIME: 10:00:00 - 11:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
In algorithmic information theory, along with the randomness of infinite sequences a relaxation of this concept - so-called partially random sequences - are considered. These partially random sequences can be characterised in several ways: by gambling systems (so-called super-martingales) and growth functions, by Martin-L"of tests or by Kolmogorov-complexity.

P. Martin-L"of had proved in 1966 that the usual (plain or simple) Kolmogorov complexity of random sequences necessarily oscillates. A similar result holds for the prefix-free variant of Kolmogorov complexity of random sequences. In contrast to this this is not true for the a priori complexity. In the talk we consider whether these oscillations can be also avoided for partially random sequences.

For a priori Kolmogorov complexity it can be shown that for every positive $varepsilon$ between 0 and 1 (inclusive) oscillation-free $varepsilon$-random sequences exist. Surprisingly, the same holds for the prefix-free variant of Kolmogorov complexity: it can be shown that for every positive $varepsilon$ between 0 to 1 (here exclusive) oscillation-free $varepsilon$-random sequences exist.

Then it is shown that the Hausdorff dimension of the set of all oscillation-free $varepsilon$-random sequences is just $varepsilon$. Finally for constructively described sets of sequences it is investigated when they contain a priori $varepsilon$-random sequences. Here the Hausdorff dimension $alpha$ of such sets is an upper bound on the possible value of $varepsilon$. If, moreover, the Hausdorff measure of those sets does not vanish, they contain $alpha$-random sequences.

BIO:
Prof. Dr. Ludwig Staiger (*1948, Jena) studied Mathematics at the Friedrich-Schiller-UniversitAt Jena (Diplom 1970, Promotion 1977, Habilitation 1979). From 1970 till 1973 he had a postgraduate study at the Yerevan State University (with Prof. R. R. Varshamov). From 1973 till 1982 he was staff member at the mathematical department of the Friedrich-Schiller-UniversitAt Jena. From 1982 till 1989 he was a scientific researcher at the Academy of Sciences in Berlin (East): at the Cental Institute of Cybernetics and Information Processes and at the Karl-WeierstraA-Institute of Mathematics. In 1989 he was Associate Professor for Algebra at the Technical University Otto-von-Guericke Magdeburg. In the years 1990 till 1995 he was visiting professor at the RWTH Aachen, the universities Dortmund, Siegen, Cottbus and again at the RWTH Aachen, and was a guest professor at the TU Wien. Since April 1, 1995 he is full professor for Theoretical Computer Science at the Martin-Luther-UniversitAt Halle-Wittenberg. From September 2000 till August 2006 he was the head of the Department for Mathematics and Computer Scinece. Dr. Staiger is external researcher of the CDMTCS and a member of the Advisory Board of the Journal of Automata, Languages and Combinatorics and of the managing commmittee of the Georg Cantor Association.

Dr. Staiger's ErdAs number is 2.