A quest for algorithmically random infinite structures

ABSTRACT

The last two decades have witnessed significant advances in the investigation of algorithmic randomness, such as Martin-Löf randomness, of infinite strings. In spite of much work, research on randomness of infinite strings has excluded the investigation of algorithmic randomness for infinite algebraic structures. The main obstacle in introducing algorithmic randomness for infinite structures is that many classes of infinite structures lack measure. More precisely, it is unclear how one would define a meaningful measure through which it would be possible to introduce algorithmic randomness for infinite structures. In this paper, we overcome this obstacle by proposing a limited amount of finiteness conditions on various classes of infinite structures. These conditions will enable us to introduce measure and, as a consequence, reason about algorithmic randomness. Our classes include finitely generated universal algebras, connected graphs and tress of bounded degree, and monoids. For all these classes one can introduce algorithmic randomness concepts and prove existence of random structures. In particular, we prove that Martin-Lóf random universal algebras, graphs, trees, and monoids exist. In the case of trees we show a stronger result that Martin-Löf random computably enumerable trees exist.

References

1. V. Bratka, J. Miller and A. Nies. Randomness and differentiability. Manuscript, 2012.
2. C. S. Calude. Information and Randomness - An Algorithmic Perspective. 2nd Edition, Revised and Extended, Springer-Verlag, Berlin, 2002. 485 pp.
3. G. J. Chaitin. On the length of programs for computing finite binary sequences: statistical considerations, Journal of the ACM, 16:145159, 1969.
4. R. Downey and D. Hirschfeldt. Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.
5. G. Grätzer, Universal Algebra, revised reprint of the second edition, Springer, New York, 2008.
6. H. Buhrman, M. Li, J. Tromp, and P. Vitanyi. Kolmogorov random graphs and the incompressibility method. SIAM J. Comput., 29(2), 590599.
7. W. Hodges. Model Theory. Encyclopaedia of Mathematics and Its Applications, No 42. Cambridge University Press, 1993.
8. A. Kolmogorov. Three approaches to the quantitative definition of information, Problems of Information Transmission 1, p.1--7, 1965.
9. M. Li and P. Vitanyi. An introduction to Kolmogorov complexity and its applications, Springer-Verlag, 3rd Edition 2008 (xx+792 pp).
10. P. Martin-Löf. The definition of random sequences, Information and Control 9(6), 602--619, 1966.
11. R. von Mises. Grundlagen der Wahrscheinlichkeitsrechnung, Mathematische Zeitschrift 5(191), 5299, 1919.
12. A. Nies. Computability and Randomness, Oxford University Press, 2009.
13. A. Nies. Personal communication.
14. C. P. Schnorr. A unified approach to the definition of random sequences, Mathematical Systems Theory 5(3):246258 (1971).
15. C. P. Schnorr. The process complexity and effective random tests, Proceedings of the fourth ACM symposium of Theory of Computing, Denver, Colorado, May 13, 1972.
16. A. K. Zvonkin and L. A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Math. Surveys, 25(6):83--124, 1970.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

  • Probability and statistics

• Theory of computation

  • Logic